題目大意

就是模板。。。沒啥好說的

思路

因為模數不互質，所以直接中國剩余定理肯定是不對的
然后就考慮怎么合并兩個同余方程
\(ans = a_1 + x_1 * m_1 = a_2 + x_2 * m_2\)
\(x_1 * m_1 + x_2 * m_2 = a _ 2 - a _ 1\)(因為正負號沒影響嘛)
然后就可以exgcd解出來\(x_1, x_2\)， 最后就可以得到\(x' = a_1 + x_1 * m_1, m' = lcm(m_1, m_2)\)
然后就不停合并就可以了

---

//Author: dream_maker #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> using namespace std; //---------------------------------------------- //typename typedef long long ll; //convenient for #define fu(a, b, c) for (int a = b; a <= c; ++a) #define fd(a, b, c) for (int a = b; a >= c; --a) #define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a) //inf of different typename const int INF_of_int = 1e9; const ll INF_of_ll = 1e18; //fast read and write template <typename T> void Read(T &x) {bool w = 1;x = 0;char c = getchar();while (!isdigit(c) && c != '-') c = getchar();if (c == '-') w = 0, c = getchar();while (isdigit(c)) {x = (x<<1) + (x<<3) + c -'0';c = getchar();}if (!w) x = -x; } template <typename T> void Write(T x) {if (x < 0) {putchar('-');x = -x; }if (x > 9) Write(x / 10);putchar(x % 10 + '0'); } //---------------------------------------------- const int N = 1e5 + 5; ll n, a[N], m[N]; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a; } void exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x = 1, y = 0; return;}exgcd(b, a % b, y, x);y -= a / b * x; } ll exCRT() {ll M = m[1], A = a[1];fu(i, 2, n) {ll d = gcd(M, m[i]), x, y;if ((a[i] - A) % d) return -1;exgcd(M, m[i], x, y);x *= (a[i] - A) / d;x = (x % (m[i] / d) + (m[i] / d)) % (m[i] / d);A += M * x, M = M / d * m[i], A %= M; }if (A < 0) A += M;return A; } int main() {while (scanf("%lld", &n) != EOF){fu(i, 1, n) Read(m[i]), Read(a[i]);Write(exCRT());putchar('\n');}return 0; }

轉載于:https://www.cnblogs.com/dream-maker-yk/p/9832310.html

總結

以上是生活随笔為你收集整理的POJ2891 Strange Way to Express Integers【扩展中国剩余定理】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。