题目链接: POJ 2891
题意:给出\(n\)对\(a_i,r_i\), 求一个最小正整数\(m\)满足\(m \equiv r_i\pmod a_i\), 或者给出无解.
solution:
\(a_i\)并不保证两两互质, 所以不能用中国剩余定理. 但可以通过数学归纳法, 用拓展欧几里得逐步得出整个线性同余方程组的解.
假设求出前\(k-1\)个方程的一个解\(m\), 记 [latex]A=lcm( a_1,a_2,…,a_{k-1}) [/latex] ,则 \(m+i*A\) 是通解. 求出满足第\(k\)个方程的\(i\), 就又求出了满足前\(k\)个方程的一个特解.
使用\(n\)次拓展欧几里得算法就能求出整个方程组的解.
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, x, y);
ll z = x;
x = y;
y = z - y * (a / b);
return d;
}
ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main() {
int k;
while (cin >> k) {
ll a,r;
cin>>a>>r;
ll x, y;
ll A=a;
exgcd(1, a, x, y);
x = x%A*r%A;
int flag = 1;
for (int i = 1; i < k; ++i) {
cin>>a>>r;
if(!flag) continue;
ll t;
ll d = exgcd(A, a, t, y);
if ((r - x) % d != 0) {
printf("-1\n");
flag = 0;
continue;
}
t = ( (t* ((r - x) / d)) % a+a )%a ;
x =x+t*A;
A = lcm(A, a);
x=x%A;
}
if (flag) cout << x << endl;
}
return 0;
}