数论好难
感觉自己数论只能记个结论(甚至结论都记不住。
如果有 x m o d m 1 = a 1 m o d m 1 x mod m_1=a_1 mod m_1 x mod m1=a1 mod m1 x m o d m 2 = a 2 m o d m 2 x mod m_2=a_2 mod m_2 x mod m2=a2 mod m2 x m o d m 3 = a 3 m o d m 3 x mod m_3=a_3 mod m_3 x mod m3=a3 mod m3 . . . . . . ... ... ...... x m o d m n = a n m o d m n x mod m_n=a_n mod m_n x mod mn=an mod mn
m 1 , m 2 . . . . . . m n m_1,m_2... ...m_n m1,m2......mn两两互素, M = m 1 × m 2 × . . . × m n M=m_1\times m_2\times ...\times m_n M=m1×m2×...×mn。那么存在解 x = ( a 1 × M 1 × M 1 − 1 + a 2 × M 2 × M 2 − 1 + . . . . . . + a i × M i × M i − 1 ) m o d M x=(a_1\times M_1\times M_1^{-1}+a_2\times M_2\times M_2^{-1}+... ...+a_i\times M_i\times M_i^{-1})mod M x=(a1×M1×M1−1+a2×M2×M2−1+......+ai×Mi×Mi−1)mod M
其中 M i = M / m i M_i=M/m_i Mi=M/mi, M i − 1 为 M i 关 于 模 m i 的 逆 元 M_i^{-1}为M_i关于模m_i的逆元 Mi−1为Mi关于模mi的逆元
练习题
AC代码:
/* * @Author: hesorchen * @Date: 2020-07-02 22:19:34 * @LastEditTime: 2020-07-03 23:04:14 * @Description: https://hesorchen.github.io/ */ #include <map> #include <set> #include <list> #include <queue> #include <deque> #include <cmath> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define endl '\n' #define PI acos(-1) #define PB push_back #define ll long long #define INF 0x3f3f3f3f #define mod 10007 #define pll pair<ll, ll> #define lowbit(abcd) (abcd & (-abcd)) #define max(a, b) ((a > b) ? (a) : (b)) #define min(a, b) ((a < b) ? (a) : (b)) #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define FRE \ { \ freopen("in.txt", "r", stdin); \ freopen("out.txt", "w", stdout); \ } inline ll read() { ll x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } //============================================================================== void exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return; } exgcd(b, a % b, x, y); ll temp = x; x = y; y = temp - (a / b) * y; } int main() { ll a[5], m[5], d, t = 1; m[1] = 23, m[2] = 28, m[3] = 33; while (cin >> a[1] >> a[2] >> a[3] >> d) { if (a[1] == a[2] && a[2] == a[3] && a[3] == d && d == -1) break; ll M = m[1] * m[2] * m[3], ans = 0, x, y, temp; temp = M / m[1]; exgcd(temp, m[1], x, y); ans += a[1] * temp * x % M; temp = M / m[2]; exgcd(temp, m[2], x, y); ans += a[2] * temp * x % M; temp = M / m[3]; exgcd(temp, m[3], x, y); ans += a[3] * temp * x % M; ans -= d; ans = (ans + M) % M; if (ans == 0) ans = M; cout << "Case " << t++ << ": the next triple peak occurs in " << ans << " days." << endl; } return 0; }