ACM算法复习篇章--数论

ACM算法复习篇章--数论

目录

一. 质数的筛法

1. 试除法

2. 埃氏筛

3. 线性筛

二. 线性筛的多种进阶用法

1. 线性筛得到不同质因子的个数

2. 线性筛得到一个数的约数个数

3. 线性筛得到一个数的约数和

三. 最大公约数与最小公倍数

---

该文章参考了《深入浅出学算法》 以及课上内容还有

筛法 - OI WikiOI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛https://oi-wiki.org/math/number-theory/sieve/线性筛 [约数个数/约数和]_ControlBear的博客-CSDN博客_线性筛约数个数刚才手动推了一下 用线性筛筛约数个数和约数和，就顺便写篇博客记录一下。不过网上应该也有不少人推过了。https://blog.csdn.net/ControlBear/article/details/77527115

一. 质数的筛法 1. 试除法

时间复杂度: O(n½)

算法原理: 假设一个合数由两个约数a , b相乘得来， 则必定有一个约数在[2 , n^(1/2)] 内， 而另一个约数在[n^(1/2), n-1]内

bool checkprime(int x)
{
    if (x == 0 || x == 1) return false;
//注意0和1的玩手特判
    for (int i = 2; i * i <= x; i++)//注意i * i 可能会爆int精度， 所以采用i <= x / i
    {
        if (x % i == 0)
        return false;
    }
    return true;
}

2. 埃氏筛

时间复杂度: O(loglogn)

算法原理: 通过一个数的比它大的倍数筛去合数

bool isprime[N];
void getprime()
{
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i * i <= N; i++)//此处与试除法同理
    {
        if (!isprime[i]) continue;
        for (int j = i*i; j <= N; j += i)
//从i*i开始是因为，在遍历2~(i-1) 时， 由于j向上枚举， 所以2*i, 3*i一直到(i-1)*i都已经判断过了
        isprime[j] = false;
    }
}

3. 线性筛

时间复杂度: O(n)

算法原理:每个合数有且仅被最小质因子筛选过

int prime[M], cnt;
bool isprime[N];
void getprime()
{
    isprime[0] = isprime[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!isprime[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= N; j++)
        {
            isprime[prime[j]*i] = 1;
            if (i % prime[j] == 0)
            break;
        }
    }
}

二. 线性筛的多种进阶用法 1. 线性筛得到不同质因子的个数

int prime[1100], d[1100], cnt;
//d数组表示不同质因子个数
bool isprime[1100];
void euler()
{
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = 0;
    for (int i = 2; i <= 1100; i++)
    {
        if (isprime[i])//如果i为质数, i的最小质因子个数有且仅有它自己本身一个
            prime[++cnt] = i, d[i] = 1;
        for (int j = 1; j <= cnt && i * prime[j] <= 1100; j++)//枚举质数
        {
            isprime[i * prime[j]] = 0;
            //一定记住每个合数都是由它的最小质因子筛除
            //if语句表示i这个数的因式分解中不包括prime[j]这个质数
            //所以prime[j]是一个新增的质因子
            if (i % prime[j])
                d[i * prime[j]] = d[i] + 1;
            else
            {
                d[i * prime[j]] = d[i];
                break;
            }
        }
    }
}

2. 线性筛得到一个数的约数个数

int c[1100], d[1100], prime[1100], cnt;
bool isprime[1100];
//c[i]表示数i的最小质因子个数， d[i]表示数i的约数个数， prime[i]表示第i个素数， isprime[i]表示数字i是不是素数
void euler()
{
    d[1] = 1;
    memset(isprime, true, sizeof(isprime));
    memset(c, 0, sizeof(c));
    for (int i = 2; i <= 1100; i++)
    {
        if (isprime[i]) prime[++cnt] = i, c[i] = 1, d[i] = 2;
        //if i为质数， 则其约数个数就是它自己加上1两个， 其最小质因子个数就是他本身那一个
        for (int j = 1; j <= cnt && i * prime[j] <= 1100; j++)
        {
            isprime[prime[j]*i] = 0;
            //同上栗， 每个约数一定是被其最小质因子筛除
            if (i % prime[j]){
                //该语句表示i的因式分解中不包含prime[j]这个质数
                //理所当然i*prime[j]的最小质因子个数就prime[j]这一个
                //由算数基本定理可知本来的 i的约数个数 num = (1+c1)*(1+c2)..(1+cn), c表示一个质数的个数
                //现在的i*prime[j]的约数个数num' = num*(1+1)
                c[i*prime[j]] = 1;
                d[i*prime[j]] = d[i]*2; 
            }
            else{
                //该语句表示i的因式分解中包括prime[j]这个质数
                //所以i*prime[j]的最小质因子个数要加1
                //由算数基本定理可知本来的 i 的约数个数num = (1+c1)*(1+c2)..(1+cn)
                //现在的i*prime[j]的约数个数num' = (1+c1+1)*(1+c2)..(1+cn);
                c[i*prime[j]] = c[i]+1;
                d[i*prime[j]] = d[i] / c[i*prime[j]] * (c[i*prime[j]]+1);
                break;
            }
        }
    }
}

3. 线性筛得到一个数的约数和

int sumd[1100], sump[1100], prime[1100], cnt;
//sumd数组表示每个数的所有约数之和， sump表示最小质因子的等比数列求和
bool isprime[1100];
void euler()
{
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= 1100; i++)
    {
        if (isprime[i]){
            //i为质数， 则i的约数有且仅有1和它本身, 所以sumd = 1+i
            //又i为它本身的最小质因子， 所以sump = i+1
            prime[++cnt] = i, sumd[i] = sump[i] = i+1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= 1100; j++)
        {
            isprime[i*prime[j]] = 0;
            if (i % prime[j]){
                //if prime[j]不是i的约数， 则说明prime[j]不包含在i的分解因式中
                //由算数基本定理， 本来i的约数和为sum = (1+p1+p1^2+..+p1^c1)*(1+p2+p2^2+...+p2^c2)...
                //现在i*prime[j]的约数和sum' = sum*(1+prime[j]);
                //而i*prime[j]的最小质因子的等比数列求和， 就是prime[j]的约数和
                sumd[i*prime[j]] = sumd[i]*sumd[prime[j]];
                sump[i*prime[j]] = sump[prime[j]];
            }
            else{
                //否则prime[j]是i的约数， 就说明prime[j]在i的分解因式中
                //由算数基本定理， 本来i的约数和为sum = (1+p1+p1^2+...+p1^c1)*(1+p2+p2^2+...+p2^c2)..
                //现在i*prime[j]的约数和sum' = (1+p1+p1^2+..+p1^c1+p1^(c1+1))..
                //所以在转移的时候将原来的最小质因子的等比数列求和除掉， 替换成新的等比数列 求和
                //而i*prime[j]的最小质因子的等比数列求和由1+p1+p1^2+...+p1^c1变成1+p1+p1^2+..+p1^c1+p1^(c1+1)
                sumd[i*prime[j]] = sumd[i]/sump[i]*(sump[i]*prime[j]+1);
                sump[i*prime[j]] = sump[i]*prime[j]+1;
                break;
            }
        }
    }
} 

三. 最大公约数与最小公倍数

算法: 辗转相除法

int gcd(int x, int y)
{
    return y ? gcd(y, x % y) : x;
}
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}

四. 分解质因数

原理: 每个数i 都能被唯一分解为 p1^c1 * p2^c2 * p3^c3...

const int N = 1e4+10;
ll p[N], c[N], cnt;
void dec(ll n)
{
    cnt = 0;
    for (ll i = 2; i *i <= n; i++)
    {
        if (n % i == 0)
        {
            p[++cnt] = i, c[cnt] = 0;
            while (n % i == 0)
                c[cnt]++, n /= i;
        }
    }
    if (n > 1) p[++cnt] = n, c[cnt] = 1;
}