学步园

关于模线性方程，可以参考我的上一篇博文。

以下叙述及证明转自：http://972169909-qq-com.iteye.com/blog/1266328 作者 KIDx

 
问题描述：给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？ 
解：采用的是合并方程的做法。 
这里将以合并第一第二个方程为例进行说明 
由上图前2个方程得(设k1、k2为某一整数)： 
 

Hdu 1573 X问题

#include <cstdio>

#define i64 __int64

i64 Md[15],w[15],n;  //w[]保存余数

i64 Extended_Euclid (i64 a,i64 b,i64 &x,i64 &y)
{//扩展欧几里得算法,求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b)
	i64 d;
	if (b==0)
	{
		x=1;y=0;
		return a;
	}
	d=Extended_Euclid(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

i64 Chinese_Remainder (i64 w[],i64 Md[],int len)
{//中国剩余定理不互质
	bool flag=false;
	i64 n1=Md[0], b1=w[0],x,y;
	for (int i=1;i<len;i++)
	{
		i64 n2=Md[i], b2=w[i];
		i64 bb=b2-b1;
		i64 d=Extended_Euclid (n1,n2,x,y);
		if (bb % d)		//模线性解k1时发现无解
		{
			flag = true;
			break;
		}
		i64 k = bb/d*x;  //相当于求上面所说的k1【模线性方程】
		i64 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 ()
{
#ifdef ONLINE_JUDGE
#else
	freopen("read.txt","r",stdin);
#endif
	int T,i,m;
	scanf("%d",&T);
	while (T--)
	{
        scanf("%d%d",&n,&m);
		for (i=0;i<m;i++)
			scanf("%I64d",&Md[i]);
		for (i=0;i<m;i++)
			scanf("%I64d",&w[i]);
		printf("%I64d\n",Chinese_Remainder(w,Md,m));
    }
	return 0;
}

Hdu 3579 Hello Kiki 

题意：n个m[i]，和n个a[i]，一个数对m[i]取模的值为a[i]，求这个数，其中m[i]之间不一定互质

#include <cstdio>

#define i64 __int64

i64 Md[10],w[10];  //w[]保存余数

i64 Extended_Euclid (i64 a,i64 b,i64 &x,i64 &y)
{//扩展欧几里得算法,求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b)
    i64 d;
    if (b==0)
    {
        x=1;y=0;
        return a;
    }
    d=Extended_Euclid(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

i64 Chinese_Remainder (i64 w[],i64 Md[],int len)
{//中国剩余定理不互质
    bool flag=false;
    i64 n1=Md[0], b1=w[0],x,y;
    for (int i=1;i<len;i++)
    {
        i64 n2=Md[i], b2=w[i];
        i64 bb=b2-b1;
        i64 d=Extended_Euclid (n1,n2,x,y);
        if (bb % d)        //模线性解k1时发现无解
        {
            flag = true;
            break;
        }
        i64 k = bb/d*x;  //相当于求上面所说的k1【模线性方程】
        i64 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 -1;  //无解
    return b1;
}

int main ()
{
#ifdef ONLINE_JUDGE
#else
    freopen("read.txt","r",stdin);
#endif
    int T,n,i;
    scanf("%d",&T);
    for (int Cas=1;Cas<=T;Cas++)
    {
        scanf("%d",&n);
        for (i=0;i<n;i++)
            scanf("%I64d",&Md[i]);
        for (i=0;i<n;i++)
            scanf("%I64d",&w[i]);
        if (n==1 && w[0]==0)  //特判只数了一次且没有剩余的情况
        {
            printf("Case %d: %d\n",Cas,Md[0]);
            continue;
        }
        printf("Case %d: %d\n",Cas,Chinese_Remainder(w,Md,n));
    }
    return 0;
}