AcWing 204. 表达整数的奇怪方式
原题链接
简单
作者:
芝居気
,
2021-12-17 16:10:13
,
所有人可见
,
阅读 209
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int n;
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;
}
ll inline mod(ll a, ll b) {
return ((a % b) + b) % b;
}
int main() {
cin >> n;
ll a1, m1;
cin >> a1 >> m1;
for (int i = 1; i < n; i++) {
ll a2, m2, k1, k2;
cin >> a2 >> m2;
ll d = exgcd(a1, -a2, k1, k2);
if ((m2 - m1) % d) { //不是最小公倍数的倍数则无法构造。
puts("-1");
return 0;
}
k1 = mod(k1 * (m2 - m1) / d, a2 /abs(d));
m1 = k1 * a1 + m1;
a1 = a1 /abs(d)* a2;
}
printf("%lld\n", m1);
return 0;
}