AcWing 204. 表达整数的奇怪方式
原题链接
中等
作者:
王子涵
,
2019-09-04 14:17:44
,
所有人可见
,
阅读 893
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL d = exgcd(b,a%b,y,x);
y -= a/b*x;
return d;
}
int main()
{
int n;
cin >>n;
LL m1,a1,x;
cin >> a1>>m1;
bool has=true;
for(int i=1;i<n;i++)
{
LL m2,a2;
cin >> a2 >> m2;
LL k1,k2;
LL d = exgcd(a1,a2,k1,k2);
if((m2-m1)%d)
{
has = false;
break;
}
k1 *=(m2-m1)/d;
LL t = a2/d;
k1 = (k1%t+t)%t;
m1 = k1 *a1 + m1;
a1 = abs(a1/d *a2);
}
if(has)
{
cout << m1<<endl;
}
else
{
cout <<-1<<endl;
}
return 0;
}