最近学习数论来着，然后就萌生了一个整理一个数论题板子集合的想法
不过，会推数学式子才是数论题的关键，数学才是数论题的基础与核心
Code:
int gcd(int a,int b) { if(a % b == 0) return a; return gcd(b,a % b); }
Exgcd:
目的是求: ax + by = gcd(a,b)的一组解(x,y)
同时返回的是d = gcd(a,b)
Code:
int Exgcd(int a,int b,int &x,int &y) { if(!b) { x = 1; y = 0; return a; } else { int d = Exgcd(b,a%b,x,y); int t = x; x = y; y = t - (a / b) * y; } }
这个算法是主要用来判断某一个数是不是质数的算法
但是请注意这个算法具有随机性，而且是单点判断，不适用于区间的素数筛选
这个算法的证明(手写)：
Code:
int gg[8] = {2,3,5,7,13,29,37,89}; Miller_Rabin(int a,int n) { int d = n - 1; int r = 0; while(d % 2 == 0) { d /= 2; r++; } int x = kuaisumi(a,d,n); if(x == 1) return true; for(int i=0;i<r;i++) { if(x == n - 1) return true; x = (long long)x * x % n; } return false; } bool is_prime(int n) { if(n <= 1) return false; for(int a=0;a<8;a++) if(n == gg[a]) return true; for(int a=0;a<8;a++) if(!Miller_Rabin(gg[a],n)) return false; return true; }
线性筛：
线性筛的算法有很多种，但是本文这里为了简便起见
只介绍欧拉筛了，同时因为欧拉筛可以预处理莫比乌斯函数和欧拉函数等数论函数
还可以得出每一个合数的最小非1因子
好处多多a
Code:
memset(not_prime,0,sizeof(not_prime)); for(int i=2;i<=n;i++) { if(!not_prime[i]) { prime[++prime_cnt] = i; phi[i] = i - 1; mu[i] = -1; } for(int j=1;j<=prime_cnt;j++) { int x = i * prime[j]; if(x > n) break; not_prime[x] = true; phi[x] = phi[i] * phi[prime[j]]; mu[x] = mu[i] * mu[prime[j]]; if(i % prime[j] == 0) { phi[x] = phi[i] * prime[j]; mu[x] = 0; break; } } }
未完待续···
原文：https://www.cnblogs.com/lyp-Bird/p/10703015.html