本文主要是介绍【中国剩余定理/扩展欧几里得定理】AcWing204.表达整数的奇怪方式——题解顺带中国剩余定理模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AcWing204.表达整数的奇怪方式
![](/upload/202206/12/202206122320315008.png)
题解
模板
![](/upload/202206/12/202206122320350599.png)
根据题目变形
![](/upload/202206/12/202206122320432338.png)
#include <iostream>
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;
LL m1, a1, x;
cin >> m1 >> a1;
for(int i = 0; i < n - 1; ++i)
{
LL m2, a2, k1, k2;
cin >> m2 >> a2;
LL d = exgcd(m1, m2, k1, k2);
if( (a2 - a1) % d )
{
x = -1;
break;
}
k1 *= (a2 - a1) / d;
k1 = (k1 % (m2 / d) + m2/d) % (m2 / d); //另k1最小使得a最小才能出现最小x
a1 = k1 * m1 + a1;
m1 = m1 / d * m2;
}
if(x != -1)
x = (a1 % m1 + m1) % m1;
cout << x << endl;
return 0;
}
这篇关于【中国剩余定理/扩展欧几里得定理】AcWing204.表达整数的奇怪方式——题解顺带中国剩余定理模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!