洛谷 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 <cstdio>
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);
}

洛谷 P3868 [TJOI2009]猜数字

原文：https://www.cnblogs.com/xuyixuan/p/11574658.html