扩张欧几里德算法

扩展欧几里德算法

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

Sample Output

欧几里德算法

概述

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
gcd函数就是用来求(a,b)的最大公约数的。
gcd函数的基本性质：
gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)
公式表述

gcd(a,b)=gcd(b,a mod b)

扩展欧几里德算法

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整
数对 x，y ，使得 gcd（a，b）=ax+by。

实现方法：

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

}

求解 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，所以递归可以结束。

这里还用了中国剩余定理，全代码：

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

int64 a[11],b[11];
int64 gcd(int64 a,int64 b,int64& x,int64& y)
{
	int64 d,t;
	if(!b)
	{
		x=1;y=0;return a;
	}
	else
	{
		gcd(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];
			gcd(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;
}

相关推荐