/*********PS:该知识点必须先学 模线性方程！！**********/
问题描述：给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？
解：采用的是合并方程的做法。
这里将以合并第一第二个方程为例进行说明
由上图前2个方程得(设k1、k2为某一整数)： 
HDU1573 X问题----可以先做下面一道纯裸题！这题在模板上 加了个 要求（符合条件）解的个数。
注释1：这里为什么要ans--呢？
原因是题目要求的数是正整数解。如果r1==0的话 显然不满足。
那么答案就要 减去一个数！
注释2：为什么要+1？
因为要把这种情况也加进来
X=b1; 即 b1%n1==b1 （b1 < n1）
//Accepted 1573 0MS 372K 1697 B G++
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
void gcd(int a,int b,int &d,int &x,int &y)
{//a*x+b*y=gcd(a,b)=d;(x,y)为其一组整数解
if(!b){d=a;x=1;y=0;}
else{ gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int main()
{
int n,m,m1,r1,m2,r2,flag=0,a[11],b[11],T;
cin>>T;
while(T--)
{
cin>>n>>m;
int i,j,k,d,x,y,c,t;
for(i=0;i<m;i++)
cin>>a[i];
for(i=0;i<m;i++)
cin>>b[i];
flag=0;
m1=a[0];r1=b[0];
for(i=1;i<m;i++)
{
m2=a[i];r2=b[i];
gcd(m1,m2,d,x,y);//d=gcd(m1,m2);x*m1+y*m2=d;
c=r2-r1;
if(c%d)//对于方程m1*x+m2*y=c，如果c不是d的倍数就无整数解
{
flag=1;
break;
}
t=m2/d;//对于方程m1x+m2y=c=r2-r1,若(x0,y0)是一组整数解,那么(x0+k*m2/d,y0-k*m1/d)也是一组整数解(k为任意整数)
//其中x0=x*c/d,y0=x*c/d;
x=(c/d*x%t+t)%t;//保证x0是正数，因为x+k*t是解，(x%t+t)%t也必定是正数解(必定存在某个k使得(x%t+t)%t=x+k*t)
r1=m1*x+r1;//新求的r1就是前i组的解，Mi=m1*x+M(i-1)=r2-m2*y(m1为前i个m的最小公倍数);对m2取余时，余数为r2；
//对以前的m取余时，Mi%m=m1*x%m+M(i-1)%m=M(i-1)%m=r
m1=m1*m2/d;
}
if(flag||n<r1)cout<<0<<endl;
else
{
int ans=(n-r1)/m1+1;//m1为ai的最小公倍数，凡是m1*i+r1的都是符合要求的数，其中r1最小-----为什么要加1？注释2
if(r1==0)ans--;//要求是正整数----看注释1！！！
cout<<ans<<endl;
}
}
return 0;
}
// 中国剩余定理的普通情况：ai不一定相互互质
还转载一个人的代码 作本题参考！
#include <iostream>
using namespace std;
#define LL __int64
#define M 10
int N;
LL Egcd (LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
LL d, tp;
d = Egcd (b, a%b, x, y);
tp = x;
x = y;
y = tp - a/b*y;
return d;
}
LL CRT2 (LL b[], LL n[], int num)
{
int i;
bool flag = false;
LL n1 = n[0], n2, b1 = b[0], b2, bb, d, t, k, x, y;
for (i = 1; i < num; i++)
{
n2 = n[i], b2 = b[i];
bb = b2 - b1;
d = Egcd (n1, n2, x, y);
if (bb % d) //模线性解k1时发现无解
{
flag = true;
break;
}
k = bb / d * x; //相当于求上面所说的k1【模线性方程】
t = n2 / d;
if (t < 0) t = -t;
k = (k % t + t) % t; //相当于求上面的K`
b1 = b1 + n1*k;
n1 = n1 / d * n2;
}
if (flag)
return 0; //无解
/******************求正整数解******************/
if (b1 == 0) //如果解为0，而题目要正整数解，显然不行
b1 = n1; //n1刚好为所有ni的最小公倍数，就是解了
/******************求正整数解******************/
if (b1 > N)
return 0;
return (N-b1)/n1+1; //形成的解：b1, b1+n1, b1+2n1,..., b1+xni...
}
int main()
{
int t, num, i, cc = 1;
LL b[M], n[M];
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &N, &num);
for (i = 0; i < num; i++)
scanf ("%I64d", n+i);
for (i = 0; i < num; i++)
scanf ("%I64d", b+i);
printf ("%I64d\n", CRT2 (b, n, num));
}
return 0;
}
HDU3579----求解线性同余方程组的 解 （最小正整数）！--其实比上一题简单，这个是纯裸题！
#include <iostream>
#include<cstdio>
using namespace std;
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(!b){d=a;x=1;y=0;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int mod(int *a,int *b,int n)
{
int i,m1,m2,r1,r2,c,d,x,y,t;
m1=a[1];r1=b[1];
for(i=2;i<=n;i++)
{
m2=a[i];r2=b[i];
c=r2-r1;
exgcd(m1,m2,d,x,y);
if(c%d) return -1;
t=m2/d;
x=(c/d*x%t+t)%t;
r1=x*m1+r1; //搞清楚最后的r1，才是满足所有方程的解！而不是x
m1=m1/d*m2; //这里求的是最小公倍数,还是先除比较不容易超出int范围。
}
if(r1==0) return m1;//当解为0，那么就要取最小公倍数；
return r1; //因为最小公倍数 去 模以所有的除数都是为0的!并且是最小解。
}
int main()
{
int T,N,i,a[8],b[8],cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%d",&a[i]);
for(i=1;i<=N;i++) scanf("%d",&b[i]);
printf("Case %d: %d\n",cas++,mod(a,b,N));
}
return 0;
}
poj2891
#include <iostream>
#include<cstdio>
using namespace std;
void exgcd(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y)
{
if(!b){d=a;x=1;y=0;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
__int64 mod(__int64 n)
{
__int64 a1,a2,b1,b2;
__int64 i,m1,m2,r1,r2,c,d,x,y,t;
__int64 flag=0;
scanf("%I64d%I64d",&a1,&b1);
m1=a1;r1=b1;
for(i=2;i<=n;i++)
{
scanf("%I64d%I64d",&a2,&b2);
if(!flag) /**这里害我RE了，即使是不存在了这样的数，
那么也要处理完输入！除非用的数组保存方式处理。**/
{
m2=a2;r2=b2;
c=r2-r1;
exgcd(m1,m2,d,x,y);
if(c%d) flag=1;
t=m2/d;
x=(x*(c/d)%t+t)%t;
r1=x*m1+r1; //搞清楚最后的r1，才是满足所有方程的解！而不是x
m1=m1/d*m2; //这里求的是最小公倍数,还是先除比较不容易超出__int64范围。
}
}
if(flag) return -1;
if(r1==0) return m1;//当解为0，那么就要取最小公倍数；
return r1; //因为最小公倍数 去 模以所有的除数都是为0的!并且是最小解。
}
int main()
{
__int64 N;
while(~scanf("%I64d",&N))
{
printf("%I64d\n",mod(N));
}
return 0;
}