AcWing 204. 表达整数的奇怪方式
原题链接
困难
作者:
Vincent_AC
,
2021-01-10 23:23:35
,
所有人可见
,
阅读 392
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y) //拓展欧几里得算法框架
{
if (!b)
{
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;
bool has_answer = true; //记录是否无解
//以下是合并的过程,每次把新的方程合并到现有方程当中
LL a1, m1;
cin >> a1 >> m1;
for (int i = 0; i < n - 1; i ++)
{
LL a2, m2;
cin >> a2 >> m2;
LL k1, k2;
LL d = exgcd(a1, -a2, k1, k2); //求最大公因数(gcd)
if ((m2 - m1) % d) //(m2 - m1)不能整除最大公因数
{
has_answer = false;
break;
}
//(m2 - m1)可以整除最大公因数
k1 *= (m2 - m1) / d; //其中的一个特解
LL t = a2 / d; //k1, k2通解的表达式
k1 = (k1 % t + t) % t; //余数变为正的
m1 = a1 * k1 + m1; //通解代回原式的m1更新
a1 = abs(a1 / d * a2); //通解代回原式的a1更新
}
if (has_answer)
{
cout << (m1 % a1 + a1) % a1 << endl;
}
else
puts("-1");
return 0;
}