#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; void exgcd(LL a,LL b,LL &x,LL &y){ if(b == 0){ x = 1, y = 0; return; } LL x1, y1; exgcd(b, a%b, x1, y1); x = y1, y = x1-a/b*y1; } LL CRT(LL a[], LL b[], LL n){ LL m = 1, ans = 0; for(int i=1;i<=n;i++)m*=a[i]; for(int i=1; i<=n; i++){ LL c = m/a[i], x, y; exgcd(c, a[i], x, y); ans = (ans+b[i]*c*x%m)%m; } return (ans%m+m)%m; } int main(){ LL n, a[11], b[11]; scanf("%lld", &n); for(int i = 1; i <= n; ++i) scanf("%lld%lld", a+i, b+i); printf("%lld\n", CRT(a,b,n)); return 0; }
标签:剩余,include,定理,long,527,y1,x1,LL From: https://www.cnblogs.com/dx123/p/16739214.html