HDU3579:Hello Kiki(解一元线性同余方程组)

时间:2021-12-06 18:31:10

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3579

题目解析:求一元线性同余方程组的最小解X,需要注意的是如果X等于0,需要加上方程组通解的整数区间lcm(a1,a2,a3,...an)。

别的就没什么注意的了。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
__int64 a,b,c,d;
__int64 X,Y;
__int64 gcd(__int64 A,__int64 B)
{
return B==?A:gcd(B,A%B);
}
void extend(__int64 A,__int64 B,__int64 &d,__int64 &x1,__int64 &y1)
{
if(B==)
{
x1=;
y1=;
d=A;
return ;
}
extend(B,A%B,d,x1,y1);
__int64 temp=x1;
x1=y1;
y1=temp-(A/B)*y1;
return ;
}
int main()
{
__int64 S[],E[];
__int64 a1,r1,a2,r2,Lcm;
__int64 T;
int m,K=;
scanf("%I64d",&T);
while(T--)
{
scanf("%d",&m);
Lcm=;
for(int i=; i<=m; i++)
{
scanf("%I64d",&S[i]);
Lcm=Lcm/gcd(Lcm,S[i])*S[i];//在一定程度上可以防止爆类型(Lcm*S[i]/gcd())
}
for(int i=; i<=m; i++)
{
scanf("%I64d",&E[i]);
}
bool ifhave=true;
a1=S[],r1=E[];
for(__int64 i=; i<=m; i++)
{
a2=S[i],r2=E[i];
a=a1;
b=a2;
c=r2-r1;
extend(a,b,d,X,Y);
if(c%d)
{
ifhave=false;
break;
}
__int64 t=b/d;
X=(X*(c/d)%t+t)%t;
X=a1*X+r1;
a1=a1*(a2/d);
r1=X;
}
printf("Case %d: ",++K);
if(!ifhave)
{
printf("-1\n");
continue;
}
if(r1==)
r1+=Lcm;
printf("%I64d\n",r1);
}
return ;
}