目录

Acwing算法基础课第四讲总结

本讲主要内容
质数,约数,欧拉函数,快速幂,扩展欧几里得算法,中国剩余定理,高斯消元,求组合数,容斥原理,博弈论。

质数

AcWing-866 试除法判定质数

原题链接

思路
实除法判定质数,复杂度为$O(\sqrt{n})$。
具体判定思路及优化思路: 由素数定义可知,小于2的数都一定不是质数。
对于大于2的数,需要判定是否能被除了1和这个数本身的数整除。 记需要判断的数为n,约数为d,由于约数一定是成对的,那么有 $d \mid n$ 且 $\frac{n}{d} \mid n$
从而对于每一对约数,有$d \leq \frac{n}{d}$
化简得$d \leq \sqrt{n}$。这表明在枚举约数时可以只枚举其中一半,从而把复杂度将至$O(\sqrt{n})$。
参考代码
#include <cstdio>

bool is_prime(int x)
{
    if(x < 2) return false;

    //这么写可以优化运行效率,并且写成除法的形式可以防止溢出
    for(int i = 2; i <= x / i; i++)
        if(x % i == 0)
            return false;

    return true;
}

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        if(is_prime(x)) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

AcWing-867 分解质因数

原题链接

思路
试除法,复杂度仍为$O(\sqrt{n})$。
注意这里在枚举时,因为是从小到大枚举,显然枚举到的因子只有质因子会被统计到,所以可以理解为枚举这个数的所有质因子。
另外有一个结论,一个正整数n最多只有一个质因数大于根号n。 由反证法,如果n有两个不同的质因数p1,p2大于根号n,那么有: $$ n \geq p_1p_2 > (\sqrt{n})^2 = n$$ 即n>n,与题设矛盾。同理大于根号n的n的质因数在n中的幂也只能是1。
证明的参考链接
参考代码
#include <cstdio>

void decompose(int x)
{
    for(int i = 2; i <= x / i; i++)
    {
        if(x % i == 0)
        {
            int f = i, s = 0;
            while(x % f == 0)
            {
                x /= f;
                s++;
            }
            printf("%d %d\n", f, s);
        }
    }

    //大于根号x的质因子只有一个,在遍历完小于根号x的质因子后,如果x还大于1,那么这时的x就是那个大于根号x的质因子
    if(x > 1)   
        printf("%d %d\n", x, 1);
    printf("\n");
}

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        if(x == 1) continue;
        else decompose(x);
    }

    return 0;
}

AcWing-868 筛质数

原题链接

思路
两种常见的筛法:埃氏筛(复杂度$O(nloglogn)$)和欧拉筛(复杂度$O(n)$)。
两种思路都主要围绕素数的倍数不是素数展开。
埃氏筛的思路是,枚举每一个质因子,并把每一个质因子的倍数筛掉,剩下的数就是素数。
欧拉筛的思路是,用最小质因子取筛掉合数。相比于埃氏筛优化的地方就在于,每个合数的最小质因子是唯一的,所以不会像埃氏筛有很多重复筛掉的地方。
参考代码

埃氏筛:

#include <cstdio>

const int maxn = 1000010;
int primes[maxn], cnt;
bool st[maxn];

void get_prime(int x)
{
    for(int i = 2; i <= x; i++)
    {
        if(st[i]) continue; //被筛掉了的不是质数,跳过
        primes[cnt++] = i;
        //下面从i*i开始筛,因为小于i*i的数字都会在[2,i)的区间中被筛掉,比如(i-1)*i,会被(i-1)给筛掉,因为它是(i-1)的i倍(不妨设i和i-1都为质数)
        for(int j = i * i; j <= x; j += i)  
            st[j] = true;
    }
}

int main(void)
{
    int n;
    scanf("%d", &n);

    get_prime(n);
    printf("%d\n", cnt);

    return 0;
}

欧拉筛:

#include <cstdio>

const int maxn = 1000010;
int primes[maxn];
bool st[maxn];
int cnt;

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        //循环条件不需要加j≤cnt,遍历升序排列的素数表找最小质因子时会及时结束循环
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;   //保证每个合数只被其最小质因子一次筛掉
        }
    }

    printf("%d\n", cnt);

    return 0;
}

约数

AcWing-869 试除法求约数

原题链接

思路
试除法,复杂度为$O(\sqrt{n})$,排序过程复杂度虽然本来为$O(nlogn)$,但是由于正整数n的约数大约有$logn$个,即排序的复杂度相比于$\sqrt{n}$可以忽略不计,所以总的平均时间复杂度仍看做$O(\sqrt{n})$。
参考代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> res;

void get_divisor(int x)
{
    for(int i = 1; i <= x / i; i++)
    {
        if(x % i == 0) 
        {
            res.push_back(i);
            if(x/i != i) res.push_back(x/i);    //排除掉按这样的方法得到一组约数相同的情况
        }
    }
    sort(res.begin(), res.end());
}

int main(void)
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        res.clear();

        get_divisor(a);
        for(auto i : res)
            printf("%d ", i);
        printf("\n");
    }

    return 0;
}

AcWing-870 约数个数

原题链接

思路
一个数N分解质因子后可以表示为(记p为质因子):
$$ N = p_1^{\alpha_1} * p_2^{\alpha_2}* \dots * p_k^{\alpha_k} $$ 而一个数的约数d都可以表示为其各质因子p的幂次项相乘:
$$ d = p_1^{\beta_1} * p_2^{\beta_2} * \dots * p_k^{\beta_k} $$ 即约数是从分解的质因数中取各幂次项组合相乘得来的,对于每个质因子的次数$\beta_i$,可以选择的数为 $0\sim\alpha_i$ 。 ,从而综合以上两式由乘法原理可知,计算一个数N的约数个数公式为:$$res_N=(\alpha_1+1)(\alpha_2+1)\dots(\alpha_k+1)$$ 用公式即可,注意约数个数在计算公式中的乘法可能会暴int,需要用long long
参考代码
#include <cstdio>
#include <unordered_map>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;

int main(void)
{
    int n;
    unordered_map<int, int> primeFactors;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        for(int i = 2; i <= a / i; i++)
        {
            while(a % i == 0)
            {
                a /= i;
                primeFactors[i]++;
            }
        }
        //一个数a只有一个大于根号a的质因子,小于等于根号a的质因子分解完若还有剩,这个因子就是大于根号a的那一个
        if(a != 1) primeFactors[a]++;
    }

    //约数的取法就是每个质因子p的位置取p的0~k次方再任意组合即可
    LL res = 1; 
    for(auto p : primeFactors) res = res * (p.second+1) % mod;
    printf("%lld\n", res);

    return 0;
}

AcWing-871 约数之和

原题链接

思路
约数之和的公式为($p_i$为质因子,$\alpha\_i$为从数N中分解出的该质因子的次数): $$res=(p_1^0+p_1^1+\dots+p_1^{\alpha_1})\dots(p_k^0+p_k^1+\dots+p_k^{\alpha_k})$$ 由于一个数的约数是由它的质因子各幂次项组合相乘而成的,所以将上式展开即可看到它就是所有约数相加的和的形式。
参考代码
#include <cstdio>
#include <unordered_map>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;

int main(void)
{
    int n;
    unordered_map<int, int> primeFactors;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        for(int i = 2; i <= a / i; i++)
        {
            while(a % i == 0)
            {
                a /= i;
                primeFactors[i]++;
            }
        }
        if(a != 1) primeFactors[a]++;
    }

    LL res = 1; 
    for(auto p : primeFactors) 
    {
        LL a = p.first, f = p.second;
        LL t = 1;
        while(f--) t = (t*a+1) % mod;
        res = res * t % mod;
    }
    printf("%lld\n", res);

    return 0;
}

AcWing-872 最大公约数

原题链接

思路
用公式即可。 记两个待求的正整数为$a$和$b$,它们的最大公约数为$d$。则有公式:
$$gcd(a,b)=gcd(b,a \% b)$$ 记$a%b=a-k*b$,其中$k=\lfloor\dfrac{a}{b}\rfloor$,且有如下等式成立:若$d\mid a$且$d\mid b$,则有$d \mid k_{1} * a+k_{2} * b$。
若$d$为$a$和$b$的公约数,则有$d\mid a$且$d\mid b$,进而$d\mid a-k*b$。故d也是$b$和$a%b$的公约数。
若$d$为$b$和$a%b$的公约数,则有$d\mid b$且$d\mid a-k*b$,结合给定成立的等式,进而$d\mid a-k*b+k*b$ 即 $d\mid a$。从而$d$也是a和b的公约数。
综上,$a$和$b$的公约数集合与$b$和$a%b$的公约数集合相同,所以他们的最大公约数也相同,所以求最大公约数的公式得证。
参考代码
#include <cstdio>

int gcd(int a, int b)
{
    return ((b==0) ? a : gcd(b, a%b));
}

int main(void)
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        int t = gcd(x, y);
        printf("%d\n", t);
    }

    return 0;
}

欧拉函数

AcWing-873 欧拉函数

原题链接

思路
参考代码

AcWing-874 筛法求欧拉函数

原题链接

思路
参考代码

快速幂

AcWing-875 快速幂

AcWing-876 快速幂求逆元

扩展欧几里得算法

AcWing-877 扩展欧几里得算法

AcWing-878 线性同余方程

中国剩余定理

AcWing-204 表达整数的奇怪方式

高斯消元

AcWing-883 高斯消元解线性方程组

AcWing-884 高斯消元解异或线性方程组

求组合数

AcWing-885 求组合数 I

AcWing-886 求组合数 II

AcWing-887 求组合数 III

AcWing-888 求组合数 IV

AcWing-889 满足条件的01序列

容斥原理

AcWing-890 能被整除的数

博弈论

AcWing-891 Nim游戏

AcWing-892 台阶-Nim游戏

AcWing-893 集合-Nim游戏

AcWing-894 拆分-Nim游戏

参考链接

zeroAC的题解