Hdu 1573 X问题 + Hdu 3579 Hello Kiki (模线性方程组-非互质中国剩余定理)

小咪咪 2022-09-17 07:30 109阅读 0赞

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

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

![ee09991f-0311-31c0-986f-a838796b7646.png][]  
**问题描述：****给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？  
解：采用的是合并方程的做法。  
这里将以合并第一第二个方程为例进行说明  
由上图前2个方程得(设k1、k2为某一整数)：**  
![5e55e37f-5abf-376a-bc59-41f9f93651a2.jpg][]  
![2ff1e981-2405-31ff-87b4-13c2d3715c03.png][]

**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;
    }

[ee09991f-0311-31c0-986f-a838796b7646.png]: /images/20220828/d8b391140a7c419988f85bb8ade4fa4a.png
[5e55e37f-5abf-376a-bc59-41f9f93651a2.jpg]: /images/20220828/391526911a6b46c1b44f52732b49056a.png
[2ff1e981-2405-31ff-87b4-13c2d3715c03.png]: /images/20220828/c957ab9e7dc24879bd8bee133b7ea50b.png