CRT【p3868】[TJOI2009]猜数字

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);

}

巴特西

CRT【p3868】[TJOI2009]猜数字

Description

Input

Output

最新文章

热门文章