首页 > 代码库 > 再说中国剩余定理、扩展欧几里德和同余方程组

再说中国剩余定理、扩展欧几里德和同余方程组

2024-07-15 05:03:19   223人阅读

E - 解同余线性方程组1
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status

Description

Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。

Input

输入包含多组测试数据。每组数据第一行包含一个整数n (n <= 10) – Andy建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000), 表示Andy建立了ai个猪圈，有bi头猪没有去处。你可以假定(ai, aj) = 1.

Output

输出包含一个正整数，即为Andy家至少养猪的数目。

Sample Input

3
3 1
5 1
7 2

Sample Output

16



在上篇博客中已经说了用中国剩余定理求同余方程组，这次又有所收获，故再详谈之。

在开始说中国剩余定理之前，再谈谈欧几里德算法和扩展欧几里德算法：

首先，欧几里德算法就是用递归的方式算两个数的最大公约数，其依据就是定理：gcd(a,b)=gcd(b,a mod b) (a>b 且 a mod b不为0)
代码就很容易了：
int gcd(int a,int b)  
{  
    if(b==0)return a;  
   
    else return gcd(b,a%b);  
 }

再次，就是扩展欧几里德算法，先看内容：
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
它也是用递归的方式实现，为什么用递归的呢？？这是由它的推导过程决定的：
求解 x，y的方法的理解
设 a>b。
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
2，ab<>0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-[a/b]*b)y2=ay2+bx2-[a/b]*by2;
也就是ax1+by1==ay2+b(x2-[a/b]*y2);
根据恒等定理得：x1=y2; y1=x2-[a/b]*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束（return a）。
再看代码：

int Egcd(int a,int b,int& x,int& y)
{
	int d,t;
	if(!b)
	{
		x=1;y=0;return a;
	}
	else
	{
		Egcd(b,a%b,y,x);
		y-=x*(a/b);
	}

}

该函数有4个参数，分别对应着 gcd（a，b）=ax+by，其中并没有关于gcd（a，b）的参数传进去（其实求出的结果是和gcd（a，b）无关的，所以无需传它的参数）
我们分别设这个4个参数为：   a：①，b：②，x：③，y：④  （注意，x，y传入的是地址，因为结果要放在x，y里）
故方程的形式：①*③+②*④=k（常数），故要想求③，把①、②、③、④按顺序放入Egcd的函数的参数中即可，便可得③。
欧几里德就说完了，接下来就是要说中国剩余定理了。

中国剩余定理简单来说就是：a = ai(mod ni),求未知数a。

设 n=n1*n2...nk, 其中因子两两互质.有:  a-----(a1,a2,...,ak), 其中ai = a mod ni, 则 a和(a1,a2,...,ak)关系是一一对应的.就是说可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a。
下面说说由(a1, a2, ..., ak)求a的方法:
定义 mi = n1*n2*...nk / ni;   ci = mi*(mf  mod ni);（在这里，很多地方写的没有那个*号，我在这加上，大家就很明了了）   其中 mi*mf  mod ni = 1;
         则 a = (a1*c1+a2*c2+...+ak*ck)      (mod n)      (注:由此等式可求a%n, 当n很大时)。
由a = (a1*c1+a2*c2+...+ak*ck)      (mod n)可知，a是由ai和ci对应相乘再相加等到的，其中在题中ai应为余数(已知），ni为除数（已知），而ci是需要算的，且ci = mi*（mf mod ni），还有 mi = n1*n2*...nk / ni（已知），所以只需且关键求出mf！！mf怎么求，别闹，上边扩展欧几里德讲了那么多，可不是白说的，来，看！

mf求法：如果理解了扩展欧几里得 ax+by=d, 就可以想到:
                     mi*mf  mod ni = 1 => mi*mf+ni*y=1;

对于这个式子 mi*mf+ni*y=1应该很熟悉吧，没错，就是用Egcd来求mf！

①：mi，②：ni，③：mf，④：y，不是想要mf吗？！把它放到③吧！

接下来就很简单了吧，看代码：

for(i=0;i<n;i++)
			s*=a[i];
		for(i=0;i<n;i++)
		{
			m=s/a[i];<span style="white-space:pre">			</span>//m表示mi
			gcd(m,a[i],x,y);
			x=(x%a[i]+a[i])%a[i];
			sum=(sum+m*b[i]*x%s)%s;<span style="white-space:pre">			</span>//这里换做用bi表示余数
		}

好了，说完了，下面是该题的全部代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
typedef __int64 int64;				//这里要用64位

int64 a[11],b[11];
int64 Egcd(int64 a,int64 b,int64& x,int64& y)
{
	int64 d,t;
	if(!b)
	{
		x=1;y=0;return a;
	}
	else
	{
		Egcd(b,a%b,y,x);
		y-=x*(a/b);
	}

}

int main()
{
	int64 sum,m,s,x,y;
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;s=1;
		for(i=0;i<n;i++)
			scanf("%I64d %I64d",&a[i],&b[i]);
		for(i=0;i<n;i++)
			s*=a[i];
		for(i=0;i<n;i++)
		{
			m=s/a[i];
			Egcd(m,a[i],x,y);
			x=(x%a[i]+a[i])%a[i];
			sum=(sum+m*b[i]*x%s)%s;
		}
		printf("%I64d\n",sum);					//既然要用64位，那输入输出也要用%I64d，否则用%d提交也会WA的。。。。
	}
	return 0;
}

这里把代码中的int 改成了int64，主要是为了保证一些比较大的数能够过。


联系
我们