求逆元，欧拉函数，中国剩余定理

求a/b的mod 等价于a*b逆的mod

求1到n的逆元可以用线性法

1 int ins[N];
2 int main() {
3     int n, p;
4     cin >> n >> p;
5     for (int i = 2; i <= n; ++i) {
6         ins[i] = (p - p / i) * ins[p % i] % p;
7     }
8     return 0;
9 }

求不连续的数组逆元

 1 const int N = 1e6 + 20;
 2 int ins[N];
 3 int a[N];
 4 int s[N];
 5 int t[N];
 6 int ans[N];
 7 int exgcd(int a, int b, int& x, int& y) {
 8     if (b == 0) {
 9         x = 1;
10         y = 0;
11         return a;
12     }
13     int d = exgcd(b, a % b, y, x);
14     y -= (a / b) * x;
15     return d;
16 }
17 int main() {
18     int n, p;
19     cin >> n >> p;
20     for (int i = 1; i <= n; ++i) {
21         cin >> a[i];
22     }
23     s[0] = 1;
24     for (int i = 1; i <= n; ++i) {
25         s[i] = a[i] * s[i - 1]%p;
26     }
27     int x, y;
28     int d=exgcd(s[n], p, x, y);
29     x = (x % p + p) % p;
30     t[n] = x;
31     ans[n] = t[n] * s[n - 1] % p;
32     for (int i = n - 1; i >= 1; --i) {
33         t[i] = t[i + 1] * a[i + 1]%p;
34         ans[i] = t[i] * s[i - 1]%p;
35     }
36     for (int i = 1; i <= n; ++i) {
37         cout << ans[i] << ' ';
38     }
39     return 0;
40 }

欧拉函数表示与x互质的数目

 1 bool b[N];
 2 int prime[N];
 3 int cnt = 0;
 4 int phi[N];
 5 int euler(int n) {
 6     for (int i = 2; i <= n; ++i) {
 7         if (!b[i]) {
 8             prime[++cnt] = i;
 9             phi[i] = i - 1;
10         }
11         for (int j = 1; j <= cnt && prime[j] * i <= n; ++j) {
12             b[prime[j] * i] = true;
13             if (i % prime[j] == 0) {
14                 phi[prime[j] * i] = phi[i] * prime[j];
15                 break;
16             }
17             else {
18                 phi[i * prime[j]] = phi[i] * phi[prime[j]];
19             }
20         }
21     }
22 }

中国剩余定理x==a[i](modm[i]) 一系列同余方程组

解法是不断合并方程组

 1 void merge(int& a, int& b, int c, int d) {
 2     int x, y;
 3     int g = exgcd(b, d, x, y);
 4     d /= g;
 5     x = (x * ((c - a) / g) % d + d) % d;
 6     a += b * x;
 7     b *= d;
 8 }
 9 int main() {
10     int a = 0, b = 1;//开局赋值0与1；
11     int n;
12     cin >> n;
13     for (int i = 1; i <= n; ++i) {
14         int c, d;
15         cin >> c >> d;
16         merge(a, b, c, d);
17     }
18     cout << a << endl;
19     return 0;
20 }