hdu1573非互素的中国剩余定理（疑似有错）

/*大牛的思路：
典型的中国剩余定理，但是这里是非互质情况下的中国剩余定理。
解题思路：
1.因为(a1,a2,a3,a4,….,ak)不一定互质，所以不能够直接用中国剩余定理。
2.x=r1+a1*k1,x=r2+a2*k2,所以有r1+a1*k1=r2+a2*k2，化简后得到 a1*k1=(r2-r1) mod(a2);
用扩展欧几里得可以得到最小的k1,所以x=r1+a1*k1+a1*a2/gcd(a1,a2)，
就这样一直替换最后剩余一个同余方程。r1就是最后的解。
对于x=a1 mod b1,x= a2 mod b2，设x=a1+m*b1
所以b1*m=a2-a1 mod b2，利用欧几里德扩展定理求出最小的非负m，
那么x=a1+m*b1就已知,且x最小，如果无解，整个同余式组无解
同时，x+k*b1是所有满足x=a1 mod b1的解，而x+k‘*b2又是所有满足x=a2 mod b2的解
那么，将x+k*b1与x+k‘*b2合并，得到的式子就是x+k*lcm(b1,b2)
于是，上面两个式子可以用x‘=x mod lcm(b1,b2)来替代
最后，就只剩下一个式子了，求得的最小的x就是答案
对于一次同余式ax=b mod n，设d=gcd(a,n)，则同余式有解的充要条件为d|b
假设d=a*x‘+n*y‘,则x0=b/d*x‘一定为方程组的一个解,且共有d个解，
（证明可以参考算法导论）最小正整数解为(x0%n/d+n/d)%(n/d)
*/
#include
#include
#include
#include
using namespace std;
typedef __int64 IntType;
IntType mod(IntType value,IntType modeNum)//求模运算，考虑负数
{
if(value <0)
value = value+((-value)/modeNum+1)*modeNum;
return value%modeNum;
}
IntType exgcd(IntType a,IntType b,IntType &x,IntType &y){//ax+by = 1
if( b == 0 ) {
x = 1;
y = 0;
return a;
}
else{
IntType x1,y1;
IntType d = exgcd ( b , mod(a,b) , x1 , y1 );
x = y1;
y= x1 - a / b * y1;
return d;
}
}
int main()
{
IntType n,m,temp;
IntType num[11],k;
IntType a[11],b[11];
IntType t;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d %I64d",&n,&m);
for(IntType i = 0; i {
scanf("%I64d",&a[i]);
}
for(IntType i = 0; i {
scanf("%I64d",&b[i]);
}
bool flag = true;
for(IntType i = 1; i {
IntType r = b[0] - b[i];
IntType k2,k1,c;
c = exgcd(a[i],a[0],k2,k1);
/*printf("gcd(%ld,%ld) = %ld\n",a[i],a[0],c);
printf("%ld * %ld = %ld (mod %d)\n",a[i],k2,c,a[0]);*/
if(mod(r,c) != 0)
{
flag = false;
break;
}
a[0] = a[0]/c*a[i];//a[0]变为lcm（a[0],a[i]）
b[0] = mod((a[i]*k2*r/c)+b[i],a[0]);
/*printf("b[0] = %ld\n",b[0]);*/
}
if(flag == false||b[0] > n)
printf("0\n");
else
{
if(b[0] == 0)
printf("%I64d\n",(n-b[0])/a[0]);
else
printf("%I64d\n",(n-b[0])/a[0]+1);
}
}
return 0;
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358917