325
HDU3579 一元线性同余方程
这题是典型的同余方程组X=Ai(mod Mi)求解问题 需要注意要求输出最小正整数
解 如果同余方程组的解是0 那么应该输出Mi的最小公倍数
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
if(b==0)
{
x=1,y=0,d=a;
return;
}
exgcd(b,a%b,d,x,y);
long long temp=x;
x=y;
y=temp-(a/b)*y;
}
long long gcd(long long a,long long b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main()
{
long long a[15],b[15],m,n,t,a1,r1,a2,r2,c,d,x,y,gc,a0,b0,s=0;
cin>>t;
while(t--)
{
bool flag=0;
gc=1;
cin>>m;
for(int i=0; i<m; i++)
cin>>b[i],gc=gc/gcd(gc,b[i])*b[i];
for(int i=0; i<m; i++)
cin>>a[i];
r1=a[0];
a1=b[0];
for(int i=1; i<m; i++)
{
a2=b[i],r2=a[i];
a0=a1,b0=a2,c=r2-r1;
exgcd(a0,b0,d,x,y);
if(c%d)
{
flag=1;
break;
}
long long t=b0/d;
x=(x*(c/d)%t+t)%t;
r1=r1+a1*x;
a1=a1*(a2/d);
}
if(flag)
{
cout<<"Case "<<++s<<": "<<-1<<endl;
continue;
}
if(r1==0)
cout<<"Case "<<++s<<": "<<gc<<endl;
else
cout<<"Case "<<++s<<": "<<r1<<endl;
}
return 0;
}
最后更新：2017-04-04 07:03:34