619
POJ 2891 解一元線性同餘方程組
這題不是中國剩餘定理 因為a1 a2..ak不互素 所以這是一道解一元線性同餘方程組的題 把兩個
等式化成一個一元線性同餘方程 迭代一下得出結果
#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;
}
int main()
{
long long k,a1,a2,r1,r2,a,b,c,x,y,d;
while(~scanf("%lld",&k))
{
bool flag=1;
scanf("%lld%lld",&a1,&r1);
for(int i=1;i<k;i++)
{
scanf("%lld%lld",&a2,&r2);
a=a1,b=a2,c=r2-r1;
exgcd(a,b,d,x,y);
if(c%d)
flag=0;
int t=b/d;
x=(x*(c/d)%t+t)%t;
r1=a1*x+r1;
a1=a1*(a2/d);
}
if(!flag)
printf("-1\n");
else
printf("%lld\n",r1);
}
return 0;
}
最後更新：2017-04-04 07:03:32