洛谷 P3868 [TJOI2009]猜数字

题意简述

给定\(a[1],a[2],\cdots,a[n]\) 和 \(b[1],b[2],\cdots,b[n]\),其中\(b\)中元素两两互素。
求最小的非负整数\(n\)，满足对于任意的\(i\)，\(n - a[i]\)能被\(b[i]\)整除。

题解思路

变形后用中国剩余定理即可，注意要快速乘。

代码

#include 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll n,x,y,lcm=1,ans;
ll a[15],p[15];
inline ll _mul(ll x,ll y,ll p) {
    ll z=(ld)x/p*y;
    ll res=(ull)x*y-(ull)z*p;
    return (res+p)%p;
}
void exgcd(const ll& a,const ll& b,ll& x,ll& y) {
	if (!b) { x=1; y=0; return; }
	exgcd(b,a%b,x,y);
	ll tmp=y; y=x-(a/b)*y; x=tmp;
}
int main() {
	scanf("%lld",&n);
	for (register int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (register int i=1;i<=n;++i) scanf("%lld",&p[i]),lcm*=p[i];
	for (register int i=1;i<=n;++i)	a[i]=(a[i]%p[i]+p[i])%p[i];
	for (register int i=1;i<=n;++i) {
		ll xx=lcm/p[i]; exgcd(xx,p[i],x,y);
		x=(x%p[i]+p[i])%p[i];
		(ans+=_mul(_mul(x,xx,lcm),a[i],lcm))%=lcm;
	}
	printf("%lld\n",ans);
}