刘汝佳训练指南——数论专题知识点总结：

￡神魔★判官ぃ 2022-08-09 12:55 150阅读 0赞

**数论是一个神奇的东西，各种结论都很经典，有些懂，有些自己还不是很懂。**

**接下来就一个一个的介绍吧。**

**第一、素数，素数本身就是一个很让人惊奇的数，因为它代表的是唯一，自己就有连个因数，一个是1，一个是自己，因为1是每个数都具备的因子（除了0），所以，它也就相当于只有自己。是一个自我感觉很良好的人呀！**

**最朴素的算法当然是从2-sqrt（2）里面找因子，如果没有，就说明它是个素数。为什么到sqrt（n）？你想，sqrt（n）\* sqrt（n）= n，而你因子的个数怎么算？是不是从1-sqrt（n）里面的因子数 \* 2？显然可得，因子数是关于sqrt（n）对称的，这边有几个那边就有几个，所以枚举一般就行！**

**高深一点，有miller-robin，前面写过这个算法，但是好像不经常用，也就没去看过了。但是有一个是比较经常用的，那就是筛法欲求范围素数。这个思想运用广泛，euler函数里面也用到了这个思想。**

**贴出筛素数的算法，一会加上miller-robin：**

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <string.h>  
3.  \#include <math.h>  
4.  \#include <iostream>  
5.  \#include <string>  
6.    
7.  **using** **namespace** std;  
8.    
9.  **const** **int** MAXN = 1000000 + 11;  
10.   
11. **bool** p\[MAXN\];  
12.   
13. **int** index\[MAXN\];  
14.   
15. **void** init()  
16. \{  
17.     memset(p, 0, **sizeof**(p));  
18.     p\[0\] = 1;  
19.     p\[1\] = 1;  
20.     **for** (**int** i = 4; i < MAXN; i += 2)  
21.     \{  
22.         p\[i\] = 1;  
23.     \}  
24.     **int** cnt = 0;  
25.     index\[cnt++\] = 2;   
26.     **for** (**int** i = 3; i < (**int**)sqrt(MAXN \* 1.0); i += 2)  
27.     \{  
28.         **if** (!p\[i\])  
29.         \{  
30.             index\[cnt++\] = i;  
31.             **int** k = i \* 2;  
32.             **for** (**int** j = k; j < MAXN; j += i)  
33.             \{  
34.                 p\[j\] = 1;  
35.             \}  
36.         \}  
37.     \}  
38.     /\* 
39.     for (int i = 0; i < cnt; i++) 
40.     \{  
41.         printf("%d\\n", index\[i\]); 
42.     \} 
43.     \*/  
44. \}  
45.   
46. **void** sieve()//这是另外一种,这种看上去简单,但是和上面的思想是一摸一样的.   
47. \{  
48.     **int** m = (**int**)sqrt(n + 0.5);  
49.     **for** (**int** i = 2; i < m; i++)  
50.     \{  
51.         **if** (!p\[i\])  
52.         \{  
53.             **for** (**int** j = i \* i; j < n; j += i)  
54.             \{  
55.                 p\[j\] = 1;  
56.             \}  
57.         \}  
58.     \}  
59. \}  
60.   
61. **int** main()  
62. \{  
63.     init();  
64.     sieve();  
65.     system("pause");  
66.     **return** 0;  
67. \}

二、欧几里德算法。欧几里德算法的精髓思想大概是辗转相除吧。还是比较好理解的，难点的就是扩展欧几里德算法，求a\*x + b\*y = gcd(a,b)；这是一个解线性方程组的最佳算法。还有一个很好的应用就是求乘法逆元，这个应用很大，因为有很多时候因为数据量非常大，都会modulo一个素数。而逆元可以把除以一个数变成乘法，这个就比较好了。

**贴出这些算法：**

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <string.h>  
3.  \#include <iostream>  
4.  \#include <string>  
5.    
6.  **using** **namespace** std;  
7.    
8.  **typedef** **long** **long** LL;  
9.    
10. **void** extgcd(LL a, LL b, LL &d, LL &x, LL &y)  
11. \{  
12.     **if** (b == 0)  
13.     \{  
14.         x = 1;  
15.         y = 0;  
16.         d = a;  
17.     \}  
18.     **else**  
19.     \{  
20.         extgcd(b, a % b, d, y, x);  
21.         y -= x \* (a / b);  
22.     \}  
23.           
24. \}  
25.   
26. LL inv(LL a, LL n)  
27. \{  
28.     LL d, x, y;  
29.     extgcd(a, n, d, x, y);  
30.     **return** d == 1 ? (x + n) % n : -1;  
31. \}  
32.   
33. **int** main()  
34. \{  
35.     **int** ans = inv(2, 5);  
36.     cout << ans << endl;  
37.     system("pause");  
38.     **return** 0;  
39. \}

三、欧拉函数phi（n）。首先就要弄明白欧拉函数求得的含义：1-n之间和n互素的数的个数。公式是

**phi(n) = n \* (1 - 1 / p1) (1 - 1 / p2) (1- 1 / p3) (1 - 1 / p4)……**

**p1,p2,p3都是n素因数分解的素因数。有了这个公式就好办了。**

**现在贴出素因数分解的代码，其实在euler\_phi函数里面就包含了这个思想，就是含有这个因子就把这个因子除尽。**

**素因数分解：**

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <string.h>  
3.  \#include <math.h>  
4.  \#include <iostream>  
5.  \#include <string>  
6.    
7.  **using** **namespace** std;  
8.    
9.  **int** main()  
10. \{  
11.     **int** N;  
12.     **while** (scanf("%d", &N) != EOF)  
13.     \{  
14.         **int** cnt = 0;  
15.         cout << "N = ";  
16.         **for** (**int** i = 2; i <= (**int**)sqrt(N + 0.5); i++)  
17.         \{  
18.             **if** (N % i == 0)  
19.             \{  
20.                 cout << i << "^";  
21.                 **while** (N % i == 0)  
22.                 \{  
23.                     N /= i;  
24.                     cnt++;  
25.                 \}   
26.                 cout << cnt << " ";  
27.             \}  
28.         \}  
29.         **if** (N > 1)  
30.         \{  
31.             cout << N << "^1";  
32.         \}  
33.         cout << endl;  
34.     \}  
35.     system("pause");  
36.     **return** 0;  
37. \}

**接下来是euler\_phi:**

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <string.h>  
3.  \#include <math.h>  
4.  \#include <iostream>  
5.  \#include <string>  
6.  /\* 
7.   \*首先你得清楚,欧拉函数的公式是什么: 
8.   \*推导出来的最简洁的公式是:phi(n) = n(1 - 1/p1)(1 - 1/p2)…… 
9.   \*这就可以轻松的求出来了  
10.  \*phi(n) 表示的含义是,不超过x且和x互素的整数个数.  
11. \*/  
12.   
13. **using** **namespace** std;  
14.   
15. **typedef** **long** **long** LL;  
16.   
17. **const** **int** MAXN = 100000 + 11;  
18.   
19. **int** phi\[MAXN\];  
20.   
21. **int** euler\_phi(**int** n)  
22. \{  
23.     LL ans = n;  
24.     **for** (**int** i = 2; i <= (**int**)sqrt(n + 0.5); i++)  
25.     \{  
26.         **if** (n % i == 0)  
27.         \{  
28.             ans = ans / i \* (i - 1);  
29.             **while** (n % i == 0)  
30.             \{  
31.                 n /= i;  
32.             \}  
33.         \}  
34.     \}  
35.     **if** (n > 1)  
36.     \{  
37.         ans = ans / n \* (n - 1);  
38.     \}  
39.     **return** ans;  
40. \}  
41.   
42. **void** phi\_table(**int** n)  
43. \{  
44.     memset(phi, 0, **sizeof**(phi));  
45.     phi\[1\] = 1;  
46.     **for** (**int** i = 2; i <= n; i++) //因为要将所有的phi都求出来,所以要循环到n,因为有一些大于sqrt(n)   
47.     \{                            //的素数还没有求出结果;   
48.         **if** (!phi\[i\])  
49.         \{  
50.             **for** (**int** j = i; j < n; j += i)  
51.             \{  
52.                 **if** (!phi\[j\])  
53.                 \{  
54.                     phi\[j\] = j;  
55.                 \}  
56.                 phi\[j\] = phi\[j\] / i \* (i - 1);  
57.             \}  
58.         \}  
59.     \}  
60. \}  
61.   
62. **void** print(**int** n)  
63. \{  
64.     **for** (**int** i = 1; i <= n; i++)  
65.     \{  
66.         printf("phi\[%d\] = %d\\n", i, phi\[i\]);  
67.     \}  
68. \}   
69.   
70. **int** main()  
71. \{  
72. //  cout << "phi(i) = " << euler\_phi(3) << endl;  
73.     phi\_table(30);  
74.     print(30);  
75.     system("pause");  
76.     **return** 0;  
77. \}

这只是最基本的算法，当然数论里面还有很多种算法，我会后续加上来的。

**四、中国剩余定理。解决多个模方程，但是变量还是一个的问题，即x = a\[i\] (% m\[i\])。方法是令M为所有的m\[i\]的乘积，wi = M / mi,则gcd(wi, mi) = 1.使得wi \* p + mi \* q = 1,可以用extgcd求出来对于wi的p解,令e =  wi \* pi,则方程组等价于方程x = e1\*a1 + e2\*a2 + e3\*a3…… 且注意x是唯一解。**

**代码如下：**

**\[cpp\]**  [view plain][] [copy][view plain]

1.  \#include <stdio.h>  
2.  \#include <string.h>  
3.  \#include <iostream>  
4.  \#include <string>  
5.  /\* 
6.   \*中国剩余定理用与解决 x = a\[i\] (% m\[i\]); 
7.   \*而m\[i\]又每每互素，将会求的唯一的最小解。  
8.   \*/   
9.    
10. **using** **namespace** std;  
11.   
12. **typedef** **long** **long** LL;  
13.   
14. **const** **int** MOD = 1000000000 + 7;  
15.   
16. **void** extgcd(**int** a, **int** b, **int** &d, **int** &x, **int** &y)  
17. \{  
18.     **if** (b == 0)  
19.     \{  
20.         d = a;  
21.         x = 1;  
22.         y = 0;  
23.     \}  
24.     **else**  
25.     \{  
26.         extgcd(b, a % b, d, y, x);  
27.         y -= x \* (a/ b);  
28.     \}  
29. \}  
30.   
31. **int** china(**int** n, **int** \*a, **int** \*m)  
32. \{  
33.     **int** M = 0;  
34.     **int** x, y, d;  
35.     **int** ans = 0;  
36.     **for** (**int** i = 0; i < n; i++)  
37.     \{  
38.         M += m\[i\];  
39.     \}  
40.     **for** (**int** i = 0; i < n; i++)  
41.     \{  
42.         **int** w = M / m\[i\];  
43.         extgcd(m\[i\], w, d, x, y);  
44.         ans = ((LL)ans + (LL)y \* w \* a\[i\]) % MOD;  
45.     \}  
46.     **return** (ans + MOD) % MOD;  
47. \}  
48.   
49. **int** main()  
50. \{  
51.     system("pause");  
52.     **return** 0;  
53. \}

[view plain]: http://blog.csdn.net/aledavvv/article/details/9942293#