用英文介绍购物网站,撤销网站备案,网站备案审核制度,h5长页面怎么制作数论是一个神奇的东西#xff0c;各种结论都很经典#xff0c;有些懂#xff0c;有些自己还不是很懂。接下来就一个一个的介绍吧。第一、素数#xff0c;素数本身就是一个很让人惊奇的数#xff0c;因为它代表的是唯一#xff0c;自己就有连个因数#xff0c;一个是1各种结论都很经典有些懂有些自己还不是很懂。接下来就一个一个的介绍吧。第一、素数素数本身就是一个很让人惊奇的数因为它代表的是唯一自己就有连个因数一个是1一个是自己因为1是每个数都具备的因子除了0所以它也就相当于只有自己。是一个自我感觉很良好的人呀最朴素的算法当然是从2-sqrt2里面找因子如果没有就说明它是个素数。为什么到sqrtn你想sqrtn* sqrtn n而你因子的个数怎么算是不是从1-sqrtn里面的因子数 * 2显然可得因子数是关于sqrtn对称的这边有几个那边就有几个所以枚举一般就行高深一点有miller-robin前面写过这个算法但是好像不经常用也就没去看过了。但是有一个是比较经常用的那就是筛法欲求范围素数。这个思想运用广泛euler函数里面也用到了这个思想。贴出筛素数的算法一会加上miller-robin[cpp] view plaincopy#include stdio.h #include string.h #include math.h #include iostream #include string using namespace std; const int MAXN 1000000 11; bool p[MAXN]; int index[MAXN]; void init() { memset(p, 0, sizeof(p)); p[0] 1; p[1] 1; for (int i 4; i MAXN; i 2) { p[i] 1; } int cnt 0; index[cnt] 2; for (int i 3; i (int)sqrt(MAXN * 1.0); i 2) { if (!p[i]) { index[cnt] i; int k i * 2; for (int j k; j MAXN; j i) { p[j] 1; } } } /* for (int i 0; i cnt; i) { printf(%d\n, index[i]); } */ } void sieve()//这是另外一种,这种看上去简单,但是和上面的思想是一摸一样的. { int m (int)sqrt(n 0.5); for (int i 2; i m; i) { if (!p[i]) { for (int j i * i; j n; j i) { p[j] 1; } } } } int main() { init(); sieve(); system(pause); return 0; } 二、欧几里德算法。欧几里德算法的精髓思想大概是辗转相除吧。还是比较好理解的难点的就是扩展欧几里德算法求a*x b*y gcd(a,b)这是一个解线性方程组的最佳算法。还有一个很好的应用就是求乘法逆元这个应用很大因为有很多时候因为数据量非常大都会modulo一个素数。而逆元可以把除以一个数变成乘法这个就比较好了。贴出这些算法[cpp] view plaincopy#include stdio.h #include string.h #include iostream #include string using namespace std; typedef long long LL; void extgcd(LL a, LL b, LL d, LL x, LL y) { if (b 0) { x 1; y 0; d a; } else { extgcd(b, a % b, d, y, x); y - x * (a / b); } } LL inv(LL a, LL n) { LL d, x, y; extgcd(a, n, d, x, y); return d 1 ? (x n) % n : -1; } int main() { int ans inv(2, 5); cout ans endl; system(pause); return 0; } 三、欧拉函数phin。首先就要弄明白欧拉函数求得的含义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 plaincopy#include stdio.h #include string.h #include math.h #include iostream #include string using namespace std; int main() { int N; while (scanf(%d, N) ! EOF) { int cnt 0; cout N ; for (int i 2; i (int)sqrt(N 0.5); i) { if (N % i 0) { cout i ^; while (N % i 0) { N / i; cnt; } cout cnt ; } } if (N 1) { cout N ^1; } cout endl; } system(pause); return 0; } 接下来是euler_phi:[cpp] view plaincopy#include stdio.h #include string.h #include math.h #include iostream #include string /* *首先你得清楚,欧拉函数的公式是什么: *推导出来的最简洁的公式是:phi(n) n(1 - 1/p1)(1 - 1/p2)…… *这就可以轻松的求出来了 *phi(n) 表示的含义是,不超过x且和x互素的整数个数. */ using namespace std; typedef long long LL; const int MAXN 100000 11; int phi[MAXN]; int euler_phi(int n) { LL ans n; for (int i 2; i (int)sqrt(n 0.5); i) { if (n % i 0) { ans ans / i * (i - 1); while (n % i 0) { n / i; } } } if (n 1) { ans ans / n * (n - 1); } return ans; } void phi_table(int n) { memset(phi, 0, sizeof(phi)); phi[1] 1; for (int i 2; i n; i) //因为要将所有的phi都求出来,所以要循环到n,因为有一些大于sqrt(n) { //的素数还没有求出结果; if (!phi[i]) { for (int j i; j n; j i) { if (!phi[j]) { phi[j] j; } phi[j] phi[j] / i * (i - 1); } } } } void print(int n) { for (int i 1; i n; i) { printf(phi[%d] %d\n, i, phi[i]); } } int main() { // cout phi(i) euler_phi(3) endl; phi_table(30); print(30); system(pause); return 0; } 这只是最基本的算法当然数论里面还有很多种算法我会后续加上来的。四、中国剩余定理。解决多个模方程但是变量还是一个的问题即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 plaincopy#include stdio.h #include string.h #include iostream #include string /* *中国剩余定理用与解决 x a[i] (% m[i]); *而m[i]又每每互素将会求的唯一的最小解。 */ using namespace std; typedef long long LL; const int MOD 1000000000 7; void extgcd(int a, int b, int d, int x, int y) { if (b 0) { d a; x 1; y 0; } else { extgcd(b, a % b, d, y, x); y - x * (a/ b); } } int china(int n, int *a, int *m) { int M 0; int x, y, d; int ans 0; for (int i 0; i n; i) { M m[i]; } for (int i 0; i n; i) { int w M / m[i]; extgcd(m[i], w, d, x, y); ans ((LL)ans (LL)y * w * a[i]) % MOD; } return (ans MOD) % MOD; } int main() { system(pause); return 0; }
