目录

• 质数
• 约数
• 同余
• 矩阵乘法
• 高斯消元与线性空间
• 组合计数
• 容斥原理
• 简单博弈论

质数

谈到质数大家绝对不会陌生，在判定一个数是个否为质数的过程中，我们最开始接触的就是试除法时间复杂度为$O(\sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
bool is_prime(int n)//判断某个数n是否为素数
{
    if(n<2)return 0;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)return 0;
    }
    return 1;
}

Eratosthenes筛法

时间复杂度很接近线性

int v[N];//v[i]表示i是否为素数
void a_primes(int n)//埃氏筛法
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++)
    {
        if(v[i])continue;
        cout<<i<<endl;
        for(int j=i;j<=n/i;j++)
        {
            v[i*j]=1;
        }
    }
}

线性筛素数（欧拉筛）

线性筛的步骤如下

1.依次考虑2~n中的每个数i；
2.如果v[i]=i,说明i是质数，把它保存下来。
3.扫描不大于v[i]的每个质数p，令v[i*p]=p。就是在筛去i与不超过i的最小质因子的质数乘积。

时间复杂度是$O(n)$

//欧拉筛
int v[N],p[N];//我们用v[i]，存储i的最小质因子，如果i=v[i],那么i为质数，p依次储存素数用于后面的筛除
void o_primes(int n)//思想：循环筛除小于等于该数最小质因子的质数与该数的乘积
{
    memset(v,0,sizeof(v));
    m=0;//质数的数量
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++)
        {
            if(prime[j]>v[i]||prime[j]*i>n)break;
            v[i*prime[j]]=prime[j];
        }
    }
    for(int i=1;i<=m;i++)cout<<prime[i]<<endl;
}

试除法分解质因数

int p[N],c[N];//p数组用来储存n分解为的质因子，c数组用来记录每个质因子的个数。
void divide(int n)
{
    m=0;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            p[++m]=i,c[m]=0;
            while(n%i==0)n/=i,c[m]++;
        }
    }
    if(n>1)p[++m]=n,c[m]=1;
    for(int i=1;i<=m;i++)
    {
        cout<<p[i]<<"^"<<c[i]<<endl;
    }
}

约数

用试除法求N的正约数集合

首先我们可以知道，如果i是n的约数，那么n/i也一定是n的约数。即约数总是成对出现的。因此我们只需要扫描1~根号n即可,时间复杂度为根号n

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int factor[N],m=0;//factor表示因数的集合，m表示约数的个数
void divisor(int n)
{
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            factor[++m]=i;
            if(i!=n/i)factor[++m]=n/i;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    divisor(n);
    for(int i=1;i<=m;i++)
    {
        cout<<factor[i]<<endl;
    }
    return 0;
}