目录
- 质数
- 约数
- 欧拉函数
- 快速幂
- 扩展欧几里得算法
- 组合数
- 博弈论
质数
分解质因数
一个数最小的因子一定是质数。
for (int i = 2; i <= x / i; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;筛质数
普通筛：
for(int i=2;i<=n;i++)
{if(!st[i]) prime[cnt++]=i;for(int j=i;j<=n;j+=i)//合数也进行操作{st[i]=true;}
}埃氏筛法：
for(int i=2;i<=n;i++)
{if(!st[i]){prime[cnt++]=i;for(int j=i;j<=n;j+=i) st[j]=true;//利用质数筛合数}
}线性筛：
for(int i=2;i<=n;i++){if(!st[i])primes[cnt++]=i;for(int j=0;primes[j]*i<=n;j++)//用最小质因子筛{st[primes[j]*i]=true;if(i%primes[j]==0)break;}}约数
每一个约数都可以由质数因子组成。
约数的个数 :
质数因子的指数+1的乘积
约数的和：
每个质因子的0-c次方的和 的乘积
最大公约数
辗转相除法：
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}欧拉函数
1-N中与N互质的数的个数即为N的欧拉函数
快速幂
快速求解a^k mod p。
把k表示为二进制的形式，那么就只要求：a1,a2,a^4…这些数mod p的值的乘积
快速幂求逆元
b在mod p的情况下的逆元即为b^(p-2)%p。
扩展欧几里得算法
ax+by=gcd(a,b),求整数x,y。
int exgcd(int a,int b,int &x,int &y)
{if(b==0)//基情况{x=1;y=0;return a;}else{int d= exgcd(b,a%b,y,x);y-=a/b*x;return d;}
}组合数
递归，预处理求出阶乘与阶乘的逆元,lucas定理
long long C(int x,int y)
{
long long res=1;
for(int i=x,j=1;j<=y;i–,j++)
{
res=res*i/j;
}return res;博弈论
必胜状态与必败状态。
sg（x1）sg（x2）…^sg（xn）如果等于零则必败，反之必胜
失败状态的sg=0;
mex函数是求没有出现过的最小的自然数
本支的sg是分支的sg值中没有出现过的最小自然数。
int sg(int x)
{if(f[x]!=-1) return f[x];//记忆化搜索unordered_set<int >S;//记录各分支的sgfor(int i=1;i<=k;i++){if(x>=op[i])S.insert(sg(x-op[i]));//有分支，则计算各分支的sg}for(int i=0;;i++){if(!S.count(i)){return f[x]=i;//本支则为mex（mex:最小的没出现过的自然数）}}}