POJ2891 (Strange Way to Express Integers)[中国剩余定理] 发表于 2018-08-27 | 更新于 2020-07-30 | | 阅读次数: 题目链接:http://poj.org/problem?id=2891 这题是中国剩余定理模板题(余数不保证互素的情况)。这里直接贴上模板。 123456789101112131415161718192021222324252627282930313233#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int maxn=1000009;int n;LL a[maxn],r[maxn];void gcd(LL a,LL b,LL& d,LL& x, LL& y) { if(!b) { d=a;x=1;y=0; } else { gcd(b,a%b,d,y,x); y-=x*(a/b); }}LL china(int n) { LL M=a[0],R=r[0],x,y,d; for(int i=1;i<n;i++) { gcd(M,a[i],d,x,y); if((R-r[i])%d!=0) return -1; x=(R-r[i])/d*x%a[i]; R-=x*M; M=M/d*a[i]; R%=M; } return (R%M+M)%M;}int main() { while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%I64d%I64d",a+i,r+i); } printf("%I64d\n",china(n)); }}