洛谷P3868（中国剩余定理,快速乘）

题目链接

根据题意，有$n-a_i\equiv 0(modbi)$ 根据同余变换法则，可以得到$n\equiv a_i(modbi)$，这就是一个中国剩余定理裸题了。

另外，$1e8\times 1e8$爆$longlong$的问题，可以使用快速乘解决，快速乘和快速幂原理相同，快速幂是$b$个$a$相乘，快速乘则是$b$个$a$相加，将乘法变换成加法处理，自然不会爆$longlong$了。

AC代码：

/* * @Author: hesorchen * @Date: 2020-07-02 22:19:34 * @LastEditTime: 2020-07-04 08:21:41 * @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; } ll ksc(ll a, ll b, ll p) //快速乘 { ll res = 0; while (b) { if (b & 1) res = (res + a) % p; a = (a + a) % p; b /= 2; } return res; } ll a[15], b[15]; int main() { ll k, M = 1; cin >> k; for (int i = 1; i <= k; i++) cin >> a[i]; for (int i = 1; i <= k; i++) cin >> b[i], M *= b[i]; ll x, y, ans = 0, temp; for (int i = 1; i <= k; i++) { ll Mi = M / b[i]; exgcd(Mi, b[i], x, y); ans += ksc((x % M + M) % M, ksc((a[i] % M + M) % M, Mi, M), M); } cout << (ans % M + M) % M << endl; return 0; }