算法数学基础

一：质数

1：判断是否是质数——试除法：

bool isprimer(int n)
{
    if (n<2)
    {
        return false;
    }
    for (int i=2; i<=n/i; i++)//优化后只枚举到根号n;
    {
        if (n%i==0)
        {
            return false;
        }
    }
    return true;
}

2：质数筛——求1-n中质数的个数

可以使用预处理的方法，将1-n中所有的质数预先存到一个数组中。

P3383 【模板】线性筛素数 - 洛谷

const int N=100000005;
int primer[N],cnt;
bool st[N];
void get_primers(int n)
{
    for (int i=2; i<=n; i++)
    {
        if (!st[i]) primer[cnt++]=i;
        for (int j=0;primer[j]<=n/i;j++)
        {
            st[primer[j]*i]=true;//将质数的所有倍数都筛掉
            if (i%primer[j]==0) break;
        }
    }
}

二、约数

1：求一个数的所有约数——同样是试除法

P1403 [AHOI2005] 约数研究 - 洛谷（没ac版）

int get_divisors(int n)
{
    vector<int>res;
    for (int i=1; i<=n/i; i++)
    {
        if (n%i==0)
        {
            res.push_back(i);
            if (i!=n/i) res.push_back(n/i);
        }
    }
    return res.size();
}

2：辗转相除法求最大公约数——gcd

P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题 - 洛谷

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

三、快速幂算法

快速求出a的k次方mod p的结果

int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if (k&1)
        {
            res=(ll)res*a%p;
        }
        k>>=1;
        a=(ll)a*a;
    }
    return res;
}

四、求组合数

就是我们高中常求的C几几。

P2822 [NOIP 2016 提高组] 组合数问题 - 洛谷

同样运用了预处理的思想，先将1-n的所有组合可能求出来，放到数组里

int c[N][N];

void init(int k)
{
    for (int i=0; i<N;i++)
    {
        for (int j=0; j<=i; j++)
        {
            if (!j)
            {
                c[i][j]=1;
            }
            else{
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
            }
        }
    }
}