中国剩余定理+模板-一一网

【摘要】中国剩余定理是一种用于求解诸如形式的同余方程组的最小非负整数解x的定理，其中，a1,a2,…,an两两互质。解法：大佬博客令 M=a1a2…an Mi= M / ai(1<=i<=n) Mi ti=1(mod ai)，ti为Mi在模ai下的逆元。因为Mi与ai一定互质，但ai不一定为质数，可以用拓展欧几里得求逆元，不能用费马小定理求。由此构造一个解 x0=…

中国剩余定理是一种用于求解诸如
图片[1]-中国剩余定理+模板-一一网
形式的同余方程组的最小非负整数解x的定理，其中，a₁,a₂,…,a_n两两互质。
解法：
大佬博客
令
M=a₁a₂…a_n
M_i= M / a_i(1<=i<=n)
M_i t_i=1(mod a_i)，t_i为M_i在模a_i下的逆元。
因为M_i与a_i一定互质，但a_i不一定为质数，可以用拓展欧几里得求逆元，不能用费马小定理求。
由此构造一个解 x₀= b₁ M₁ t₁+ b₂ M₂ t₂+…+b_n M_n t_n；任意解即为x=x₀+k*M,最小正整数解为x%M。
模板题：洛谷P1495
题目链接
code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;

int m[maxn], a[maxn];
ll ret = 1;
int n;

void exgcd(ll a,ll b,ll &x,ll &y)
{ if(!b){ x = 1, y = 0; return; } exgcd(b, a % b, x, y); ll t = x; x = y, y = t - (a / b) * y;
}

int main()
{ ll ans = 0; scanf("%d", &n); for (int i = 1; i <= n;i++){ scanf("%d%d", &m[i], &a[i]); ret = ret * m[i]; } for (int i = 1; i <= n;i++){ ll s = ret / m[i]; ll x = 0, y = 0; exgcd(s, m[i], x, y); if(x<0) x += m[i]; ans += s * x * a[i]; } ans = ans % ret; printf("%lld\n", ans); return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57