【数论】【扩展欧几里得】hdu3579 Hello Kiki

解一元线性同余方程组（模数不互质）

结合看这俩blog讲得不错

http://46aae4d1e2371e4aa769798941cef698.devproxy.yunshipei.com/qq_27599517/article/details/50887445

上面这个对于理解为什么要用最小公倍数有帮助

http://blog.csdn.net/thearcticocean/article/details/49452859

思路就是不断两两合并，成一元线性同余方程，然后不断用扩欧求解

由于是最小的正整数解，而非非负整数解，所以最后答案如果是0，要加上模数的最小公倍数

#include<cstdio>

using namespace std;

int a[10],r[10],T,n;

void exgcd(int a,int b,int &d,int &x,int &y)

{

    if(!b)

      {

        d=a;

        x=1;

        y=0;

      }

    else

      {

        exgcd(b,a%b,d,y,x);

        y-=x*(a/b);

      }

}

int main(){

//	freopen("c.in","r",stdin);

	scanf("%d",&T);

	for(int zu=1;zu<=T;++zu){

		scanf("%d",&n);

		for(int i=1;i<=n;++i){

			scanf("%d",&a[i]);

		}

		for(int i=1;i<=n;++i){

			scanf("%d",&r[i]);

		}

		int a1=a[1],r1=r[1];

		for(int i=2;i<=n;++i){

			int a2=a[i],r2=r[i];

			int d,x0,y0;

			int c=r2-r1;

			exgcd(a1,a2,d,x0,y0);

			if(c%d){

				r1=-1;

				break;

			}

			int t=a2/d;

			x0=(x0*(c/d)%t+t)%t;

			r1=a1*x0+r1;

			a1=a1*(a2/d);

		}

		printf("Case %d: %d\n",zu,r1==0 ? r1+a1 : r1);

	}

	return 0;

}

巴特西

【数论】【扩展欧几里得】hdu3579 Hello Kiki

最新文章

热门文章