数论模板

1.中国剩余定理 (互质版)

#include <iostream>
using namespace std;
typedef long long LL;
LL ex_gcd(LL a, LL b, LL &x, LL &y);
LL China(LL re[], LL w[], LL len);

int main()
{
  LL n, i;
  LL a[50000], b[50000];
  while (cin >> n)
  {
    for (i = 0; i < n; i++)
    {
      cin >> a[i] >> b[i];//除数，余数
    }
    cout << China(b, a, n) << endl;
  }
  return 0;
}

LL ex_gcd(LL a, LL b, LL &x, LL &y)//扩展gcd
{
  LL d = 0;
  if (b == 0)
  {
    x = 1; y = 0;
    return a;
  }
  d = ex_gcd(b, a%b, y, x);
  y -= a / b * x;
  return d;
}

LL China(LL re[], LL w[], LL len)//中国剩余原理  re余数数组 w除数数组 len数组长度
{
  LL i, d, x, y, m, n, ret;
  ret = 0;
  n = 1;
  for (i = 0; i < len; i++)
    n *= w[i];
  for (i = 0; i < len; i++)
  {
    m = n / w[i];
    d = ex_gcd(w[i], m, x, y);
    ret = (ret + y * m*re[i]) % n;
  }
  return (n + ret % n) % n;
}

2.中国剩余原理（万能版）

慢一点的：

#include<iostream>
#include<stdio.h>
using namespace std;
long long exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  long long q = exgcd(b, a%b, y, x);
  y -= a / b * x;
  return q;
}
int main() {
  long long a1, c1, a2, c2, x, y, t;
  long long n;
  while (cin >> n) {
    long long flag = 1;
    cin >> a1 >> c1;
    for (long long i = 1; i < n; i++) {
      cin >> a2 >> c2;
      long long q = exgcd(a1, a2, x, y);
      if ((c2 - c1) % q != 0) {
        flag = 0;
      }
      t = a2 / q;
      x = ((x*(c2 - c1) / q) % t + t) % t;
      c1 = c1 + a1 * x;
      a1 = a1 * (a2 / q);
    }
    if (flag == 0) {
      cout << "-1" << endl;
      continue;
    }
    cout << c1 << endl;
  }
  return 0;
}

快一点的：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;
typedef long long LL;

LL gcd(LL a, LL b)
{
  if (b == 0)
    return a;
  return gcd(b, a%b);
}

LL ex_gcd(LL a, LL b, LL&x, LL& y)
{
  if (b == 0)
  {
    x = 1, y = 0;
    return a;
  }
  LL d = ex_gcd(b, a%b, x, y);
  LL t = x;
  x = y;
  y = t - a / b * y;
  return d;
}


LL inv(LL a, LL n)//求a在模n乘法下的逆元，没有则返回-1  
{
  LL x, y;
  LL t = ex_gcd(a, n, x, y);
  if (t != 1)
    return -1;
  return (x%n + n) % n;
}

//将两个方程合并为一个  
bool merge(LL a1, LL n1, LL a2, LL n2, LL& a3, LL& n3)
{
  LL d = gcd(n1, n2);
  LL c = a2 - a1;
  if (c%d)
    return false;
  c = (c%n2 + n2) % n2;
  c /= d;
  n1 /= d;
  n2 /= d;
  c *= inv(n1, n2);
  c %= n2;
  c *= n1 * d;
  c += a1;
  n3 = n1 * n2*d;
  a3 = (c%n3 + n3) % n3;
  return true;
}

//求模线性方程组x=ai(mod ni),ni可以不互质  
LL ex_China(int len, LL* a, LL* n)
{
  LL a1 = a[0], n1 = n[0];
  LL a2, n2;
  for (int i = 1; i < len; i++)
  {
    LL aa, nn;
    a2 = a[i], n2 = n[i];
    if (!merge(a1, n1, a2, n2, aa, nn))
      return -1;
    a1 = aa;
    n1 = nn;
  }
  return (a1%n1 + n1) % n1;
}
LL a[1000], b[1000];
int main()
{
  int i;
  int k;
  while (cin >> k)
  {
    for (i = 0; i < k; i++)
      cin >> a[i] >> b[i];
    cout << ex_China(k, b, a);
  }
  return 0;
}