数论部分

 

 

目录

• 质数
• 约数
• 欧拉函数
• 快速幂
• 扩展欧几里得算法
• 组合数
• 博弈论

质数

分解质因数

一个数最小的因子一定是质数。

 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表示为二进制的形式，那么就只要求：a^1,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:最小的没出现过的自然数）}}}