Description
现有两组数字，每组k个，第一组中的数字分别为：a1，a2，...，ak表示，第二组中的数字分别用b1，b2，...，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。
Input
输入数据的第一行是一个整数k，（1 ≤ k ≤ 10）。接下来有两行，第一行是：a1，a2，...，ak，第二行是b1，b2，...，bk
Output
输出所求的整数n。
\(CRT\)。
通过读题，我们可以得到一群这样的关系
\[n-a_i \equiv 0(mod \ b_i)
\]
\]
然后移项
\[n \equiv a_i(mod \ b_i)
\]
\]
\(What's \ this?\)中国剩余定理。
懒得在这推了,所以就是裸的\(CRT\)问题了。
放下代码好了。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define R register
using namespace std;
const int gz=18;
inline void in(R int &x)
{
R int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int a[gz],b[gz],N=1,n,ans;
int exgcd(R int a,R int b,R int &x,R int &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
R int t=exgcd(b,a%b,x,y);
R int tmp=x;
x=y;y=tmp-a/b*y;
return t;
}
inline int mul(R int x,R int y)
{
R int res=0;
for(;y;y>>=1,x=(x+x)%N)
if(y&1)res=(res+x)%N;
return res;
}
inline void China()
{
for(R int i=1;i<=n;i++)
{
R int bb=N/b[i];
R int aa=b[i];
R int x,y;
exgcd(aa,bb,x,y);
(y+=b[i])%=b[i];
R int tmp=mul(bb,y)%N;
(ans+=mul(a[i],tmp)%N)%=N;
}
}
signed main()
{
in(n);
for(R int i=1;i<=n;i++)in(a[i]);
for(R int i=1;i<=n;i++)in(b[i]),N*=b[i];
China();
printf("%lld",(ans+N)%N);
}