本文共 2958 字,大约阅读时间需要 9 分钟。
现有两组数字,每组 kk 个。
第一组中的数字分别用 a 1 , a 2 , ⋯ , a k a_1,a_2,\cdots ,a_k a1,a2,⋯,ak表示,第二组中的数字分别用 b 1 , b 2 , ⋯ , b k b_1,b_2,\cdots ,b_k b1,b2,⋯,bk表示。
其中第二组中的数字是两两互素的。求最小的 n ∈ N n\in \mathbb{N} n∈N,满足对于 ∀ i ∈ [ 1 , k ] \forall i\in [1,k] ∀i∈[1,k],有 b i ∣ ( n − a i ) b_i | (n-a_i) bi∣(n−ai)第一行一个整数 kk。
第二行 kk 个整数,表示: a 1 , a 2 , ⋯ , a k a_1,a_2,\cdots ,a_k a1,a2,⋯,ak 。
第三行 kk 个整数,表示: b 1 , b 2 , ⋯ , b k b_1,b_2,\cdots ,b_k b1,b2,⋯,bk 。输出一行一个整数,为所求的答案 n。
输入
31 2 32 3 5
输出
23
对于 100 % 100\% 100% 的数据:
1 ≤ k ≤ 10 , ∣ a i ∣ ≤ 1 0 9 , 1 ≤ b i ≤ 6 × 1 0 3 , ∏ i = 1 k b i ≤ 1 0 18 1\le k \le 10,|a_i|\le 10^9,1\le b_i\le 6\times 10^3 ,\prod_{i=1}^k b_i\le 10^{18} 1≤k≤10,∣ai∣≤109,1≤bi≤6×103,∏i=1kbi≤1018
每个测试点时限 1 秒。
注意:对于 C/C++ 语言,对 64 位整型数应声明为 long long。
若使用 scanf,printf 函数(以及 fscanf,fprintf 等),应采用 %lld 标识符。
问题转化为:
⎧ ⎪ a n s ≡ a 1 ( m o d b 1 ) ⎪ a n s ≡ a 2 ( m o d b 2 ) ⎨ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⎪ a n s ≡ a n ( m o d b n ) ⎩ ⎧ \\ ⎪\ \ ans\equiv a_1(mod\ \ b_1)\\ ⎪\ \ ans\equiv a_2(mod\ \ b_2)\\ ⎨ \ \ \ \ \ \ \ \ \ ······\\ ⎪\ \ ans\equiv a_n(mod\ \ b_n)\\ ⎩ ⎧⎪ ans≡a1(mod b1)⎪ ans≡a2(mod b2)⎨ ⋅⋅⋅⋅⋅⋅⎪ ans≡an(mod bn)⎩
所以用很 再加上龟速乘解决数值大的问题即可。 CRT的做法:👆链接里的另一篇真正的模板CRT,此篇就省略了。这里讲下龟速乘(本人第一次用 )
也就是说
15即第一个乘数记为 a a a,11即第二个乘数的二进制记为 b b b。 我们从二进制的低位往高位逐位进行两个操作:若 b i = 1 b_i=1 bi=1 则 a n s + = a ans+=a ans+=a; a + = a a+=a a+=a 所以我们就这样将一个乘法活生生变成了加法,且每次加法都可以 % m o d \%mod %mod 就不用担心爆掉了。 代码如下:ll fmul(ll a,ll b,ll c){ ll sum=0; while(b) { if(b&1) sum=(sum+a)%c; //若此位为 1,则加上 a=(a+a)%c; b>>=1; //右移一位 } return sum;}
但本题还有个坑人的地方:
再仔细看看数据规模: ∣ a i ∣ ≤ 1 0 9 |a_i|\le 10^9 ∣ai∣≤109 也就是说,a可以是负数,所以要加些特别的处理(👇注释中有说),且快读要判负!#include#include #define ll long longusing namespace std;ll n,m=1,ans,t,x,y,a[20],b[20];ll read(){ int x=0,t=1; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') t=-1; c=getchar(); } while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+c-48; c=getchar(); } return x*t;}ll fmul(ll a,ll b,ll c)//龟速乘{ ll sum=0; while(b) { if(b&1) sum=(sum+a)%c; a=(a+a)%c; b>>=1; } return sum;}void exgcd(ll a,ll b)//求逆元{ if(b==0) { x=1; y=0; return; } exgcd(b,a%b); int t=x; x=y; y=t-a/b*y;}int main(){ n=read(); for(int i=1; i<=n; i++) { b[i]=read();//a,b反着输入,CRT处理习惯问题 } for(int i=1; i<=n; i++) { a[i]=read(); m*=a[i]; } for(int i=1;i<=n;i++) { b[i]=(b[i]%a[i]+a[i])%a[i];//特殊处理,以防负数 } for(int i=1; i<=n; i++) { t=m/a[i]; x=y=0; exgcd(t,a[i]); x=(x%a[i]+a[i])%a[i];//特殊处理,以防负数 ans=(ans+fmul(fmul(x,t,m),b[i],m))%m;//记得用龟速乘 } cout<
转载地址:http://ahpwb.baihongyu.com/