数论基础

扩展欧几里得

hdu2669, 解同余方程 ax+by=1

 1 int gcd(int a, int b, int& x, int& y)
 2 {
 3     if(b == 0){
 4         x = 1;
 5         y = 0;
 6         return a;
 7     }
 8     else{
 9         int temp = gcd(b, a % b, x, y);
10         int t = y;
11         y = x - y * (a / b);
12         x = t;
13         return temp;
14     }
15 }

费马小定理 gcd(a,p)=1，那么 a^(p-1) ≡1（mod p）

hdu4828,费马小定理计算卡特兰数

 1 #include <iostream>
 2 #include <cstdio>
 3 #define MAXN 2000001
 4 #define MOD 1000000007
 5 using namespace std;
 6 
 7 long long f[MAXN + 5];
 8 long long gcd(long long a, long long b, long long& x, long long& y)
 9 {
10     if(b == 0){
11         x = 1;
12         y = 0;
13         return a;
14     }
15     else{
16         long long temp = gcd(b, a % b, x, y);
17         long long t = y;
18         y = x - y * (a / b);
19         x = t;
20         return temp;
21     }
22 }
23 
24 int main()
25 {
26     f[1] = 1;
27     for(long long i = 2; i <= MAXN; i++){
28         f[i] = (f[i - 1] * (4 * i - 2)) % MOD;
29         gcd(i + 1, MOD, x, y);
30         if(x < 0){
31             x = MOD - (-x) % MOD;
32         }
33         x = x % MOD;
34         f[i] = (f[i] * x) % MOD;
35     }

中国剩余定理

hdu1573,不互素的中国剩余定理

 1 #include <iostream>
 2 #include <cstdio>
 3 #define M 11
 4 using namespace std;
 5 
 6 long long a[M], b[M];
 7 long long x, y;
 8 bool flag;
 9 long long gcd(long long  a, long long  b)
10 {
11     if (b == 0){
12         return a;
13     }
14     return gcd(b, a % b);
15 }
16 
17 long long exgcd(long long  a, long long  b, long long & x, long long & y)
18 {
19     if (b == 0){
20         x = 1;
21         y = 0;
22         return a;
23     }
24     else{
25         long long  temp = exgcd(b, a % b, x, y);
26         long long  t = y;
27         y = x - y * (a / b);
28         x = t;
29         return temp;
30     }
31 }
32 int main()
33 {
34     long long  T, d, n, m, t, A, B;
35     scanf("%I64d", &T);
36     for (int cas = 1; cas <= T; cas++){
37         flag = false;
38         scanf("%I64d%I64d", &n, &m);
39         for (int i = 1; i <= m; i++){
40             scanf("%d", &a[i]);
41             //t = (t * a[i]) / gcd(t, a[i]);
42         }
43         for (int i = 1; i <= m; i++){
44             scanf("%I64d", &b[i]);
45         }
46         A = a[1], B = b[1];
47         for (int i = 2; i <= m; i++){
48             d = exgcd(A, a[i], x, y);
49             if ((b[i] - B) % d != 0){
50                 flag = true;
51                 break;
52             }
53             x = (b[i] - B) / d * x;
54             y = a[i] / d;
55             x = (x % y + y) % y;
56             B = x * A + B;
57             A = (A * a[i]) / d;
58             B = (B % A + A) % A;
59         }
60         if (B > n || flag){
61             printf("0
");
62         }
63         else{
64             t = 1 + (n - B) / A;
65             if (B == 0){
66                 --t;
67             }
68             printf("%I64d
", t);
69         }
70     }
71 }

欧拉函数

求1-n与n互质的个数

 1 int euler(int x){
 2      int ans = x, m = n;
 3      for(int i = 2; i * i <= x; i++){
 4          if(x % i == 0){
 5              ans = ans / i * (i - 1);
 6              while(x % i == 0){
 7                     x /= i;
 8              }
 9          }
10      }
11      if(x > 1){
12             ans = ans / x * (x - 1);
13      }
14      return ans;
15 }

指数循环节