[2017.3.29]中国生育腚理不互质

好久没有写博了……今天水一水中国生育腚理不互质的情况设n₁与n₂不互质

其中gcd(n₁,n₂)|(a₂-a₁)才有解的原因如下：

设gcd(n₁,n₂)=d

n₁=d*t₁

n₂=d*t₂

∴x=k₁*t₁*d+a₁

=k₂*t₂*d+a₂

∴k₁t₁d+a₁=k₂t₂d+a₂

∴(k₁t₁-k₂t₂)d=a₂-a₁

∴gcd(n₁,n₂)|(a₂-a₁)

例题：poj2891 http://poj.org/problem?id=2891

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define eps (0.5)
 8 #define RG register
 9 using namespace std;
10 typedef long long LL;
11 LL d,k,x,y,hold,lastyu,lastmod,a[10000000],r[10000000];
12 inline LL gll(){
13     RG LL x=0;RG bool flag=0;RG char c=getchar();
14     while((c<'0'||c>'9')&&c!='-') c=getchar();
15     if(c=='-') c=getchar(),flag=1;
16     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
17     return flag?-x:x;
18 }
19 inline void e_gcd(RG LL a,RG LL b,RG LL &x,RG LL &y){
20     if(b==0){d=a;x=1;y=0;return;}
21     e_gcd(b,a%b,x,y);
22     hold=x;x=y;y=hold-a/b*y;
23 }
24 inline LL fbc(RG LL a,RG LL b,RG LL mod){return (a*b-(LL)((double)a/mod*(double)b+eps)*mod+mod)%mod;}
25 inline LL China(){
26     for (RG int i=1;i<=k;++i){
27     e_gcd(lastmod,a[i],x,y);
28     if((r[i]-lastyu)%d) return -1;
29     LL gcd=d;
30     e_gcd(lastmod/gcd,a[i]/gcd,x,y);
31     LL now=fbc((r[i]-lastyu)/gcd,x,a[i]/gcd);
32     lastyu=(lastyu+fbc(now,lastmod,lastmod/gcd*a[i]))%(lastmod/gcd*a[i]);
33     lastmod=lastmod/gcd*a[i];
34     }
35     if(lastyu<0) lastyu+=lastmod;
36     return lastyu;
37 }
38 inline void work(){
39     for (RG LL i=1;i<=k;++i){
40     a[i]=gll();
41     r[i]=gll();
42     }
43     lastyu=r[1];lastmod=a[1];
44     printf("%lld
",China());
45 }
46 int main(){
47     while(scanf("%lld",&k)!=EOF) work();
48     return 0;
49 }

View Code