因倍质合（1）小学奥数的噩梦

我觉得这篇分享配得上大佬们的赞。

（我的年龄众所周知

因倍质合，相信都是大家小学中学时的阴影……

各种公式定理证明模型……

如果你觉得它很简单，请看下面的列表。

表格完成。
正式开始。

$\color{#7FFF00}{距看完最后两讲的人透露，他们的肤色跟这行字的颜色一样一样的。}$

你看，脸都绿了。

1、试除法判定质数——暴力出奇迹。

首先粘上题目。
给定n个正整数ai，判定每个数是否是质数。

输入格式
第一行包含整数n。

接下来n行，每行包含一个正整数ai。

输出格式
共n行，其中第 i 行输出第 i 个正整数ai是否为质数，是则输出“Yes”，否则输出“No”。

数据范围
$ 1≤n≤100,\\\ 1≤ai≤2∗{10}^9 $
输入样例：

2
2
6

输出样例：

Yes
No

本题就是判断质数。
首先声明一下什么是因倍质合以及一些基础的定理的证明。
如下：

因数：

设一个数为a，则这个数的因数x满足：
$$ a \mod x \equiv 0 $$

倍数：

设一个数为a，则这个数的倍数x满足：
$$ x \mod a \equiv 0 $$

质数：

一个数x如果只有两个因数，则x为质数

合数：

一个数x如果有两个以上（不包括两个），则x为合数

1：

既不算质数也不算合数，因为1只有一个因数。

简单公式和必备知识：

1、因数个数定理

简单一句话：指数加一连成积。
这里来一个具体的例子。

前方高能！！！

$$ \\\ x = {p_1} ^ {\alpha_1} \times {p_2} ^ {\alpha_2} \times \cdots \times {p_n} ^ {\alpha_n}\\\ 则x的因数个数 = (\alpha_1 + 1) \times (\alpha_2 + 1) \times \cdots \times (\alpha_n + 1)\\\ \\\ $$

100以内质数表：

加粗体的是质数。

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99

共25个质数。
上面是手打的，并没有使用c++！！！

因数和定理

定理公式：

$x[n] = ({p_1} ^ 0 + {p_1} ^ 1 + {p_1 ^ 2} + \cdots {p_1} ^ {a_1}) \times ({p_2} ^ 0 + {p_2} ^ 1 + {p_2} ^ 2 + \cdots p_2 ^ {a_2}) \cdots ({p_k} ^ 0 + {p_k} ^ 1 + {p_k} ^ 2 + \cdots {p_k} ^ {a_k})$

感谢@垫底抽风帮忙调试Markdown代码！！！

这里提供一版百度百科的简洁证明：

$$ 设n的分解质因数为：\\\ n = {p_1} ^ {\alpha_1} \times {p_2} ^ {\alpha_2} \times \cdots \times {p_n} ^ {\alpha_n}\\\ 则 {p_1} ^ {\alpha_1} 的因数有：\\\ {p_1} ^ 0, {p_1} ^ 1, \cdots {p_1} ^ {\alpha_1}\\\ 同理，{p_x} ^ {\alpha_x}的因数有：\\\ {p_x} ^ 0, {p_x} ^ 1, \cdots {p_x} ^ {\alpha_x}\\\ 由乘法原理可得：\\\ x[n] = ({p_1} ^ 0 + {p_1} ^ 1 + {p_1 ^ 2} + \cdots {p_1} ^ {a_1}) \times ({p_2} ^ 0 + {p_2} ^ 1 + {p_2} ^ 2 + \cdots p_2 ^ {a_2}) \cdots ({p_k} ^ 0 + {p_k} ^ 1 + {p_k} ^ 2 + \cdots {p_k} ^ {a_k})\\\ $$

100以内所有合数的分解质因数：

建议各位数学党做到秒分。
下面可能有些许笔误，欢迎各位大佬在留言区指正。
$$ 4 = 2 ^ 2\\\ 6 = 2 \times 3\\\ 8 = 2 ^ 3\\\ 9 = 3 ^ 2\\\ 10 = 2 \times 5\\\ 12 = 2 ^ 2 \times 3\\\ 14 = 2 \times 7\\\ 15 = 3 \times 5\\\ 16 = 2 ^ 4\\\ 18 = 2 \times 3 ^ 2\\\ 20 = 2 ^ 2 \times 5\\\ 21 = 3 \times 7\\\ 22 = 2 \times 11\\\ 24 = 2 ^ 3 \times 3\\\ 25 = 5 ^ 2\\\ 26 = 2 \times 13\\\ 27 = 3 ^ 3\\\ 28 = 2 ^ 2 \times 7\\\ 30 = 2 \times 3 \times 5\\\ 32 = 2 ^ 5\\\ 33 = 3 \times 11\\\ 34 = 2 \times 17\\\ 35 = 5 \times 7\\\ 36 = 2 ^ 2 \times 3 ^ 3\\\ 38 = 2 \times 19\\\ 39 = 3 \times 13\\\ 40 = 2 ^ 3 \times 5\\\ 42 = 2 \times 3 \times 7\\\ 44 = 2 ^ 2 \times 11\\\ 45 = 3 ^ 3 \times 9\\\ 46 = 2 \times 23\\\ 48 = 2 ^ 4 \times 3\\\ 50 = 2 \times 5 ^ 2\\\ 51 = 3 \times 17\\\ 52 = 2 ^ 2 \times 13\\\ 54 = 2 \times 3 ^ 3\\\ 55 = 5 \times 11\\\ 56 = 2 ^ 3 \times 7\\\ 57 = 3 \times 19\\\ 58 = 2 \times 29\\\ 60 = 2 ^ 2 \times 3 \times 5\\\ 62 = 2 \times 31\\\ 63 = 3 ^ 2 \times 7\\\ 64 = 2 ^ 6\\\ 65 = 5 \times 13\\\ 66 = 2 \times 3 \times 11\\\ 68 = 2 ^ 2 \times 17\\\ 69 = 3 \times 23\\\ 70 = 2 \times 5 \times 7\\\ 72 = 2 ^ 3 \times 3 ^ 2\\\ 74 = 2 \times 3 \times 13\\\ 75 = 3 \times 5 ^ 2\\\ 76 = 2 ^ 2 \times 19\\\ 77 = 7 \times 11\\\ 78 = 2 \times 3 \times 13\\\ 80 = 2 ^ 4 \times 5\\\ 81 = 3 ^ 4\\\ 82 = 2 \times 41\\\ 84 = 2 ^ 2 \times 3 \times 7\\\ 85 = 5 \times 13\\\ 86 = 2 \times 43\\\ 87 = 3 \times 29\\\ 88 = 2 ^ 3 \times 11\\\ 90 = 2 \times 3 ^ 2 \times 5\\\ 91 = 7 \times 13\\\ 92 = 2 ^ 2 \times 23\\\ 93 = 3 \times 31\\\ 94 = 2 \times 37\\\ 95 = 5 \times 19\\\ 96 = 2 ^ 5 \times 3\\\ 98 = 2 \times 7 ^ 2\\\ 99 = 3 ^ 2 \times 11\\\ 100 = 2 ^ 2 \times 5 ^ 2\\\ $$
密集恐惧症患者cht已逃走……

快速判断是否是100以内的质数小技巧

100以内的合数都跟2,3,5,7有关。
因为$11 \times 11 = 121,121 > 100$。

回到刚刚那道题，我们总结一下质数的性质：

质数的性质：

1不是质数
2是质数
所有只有两个因数的数是质数。

所以我们就可以写出判断质数的最暴力的代码乐！

int is_prime(int x)
{
    if(x == 1) return 0;
    if(x == 2) return 1;
    for(int i = 2; i <= x; i ++)
    {
        if(x % i == 0) return 0;
    }
    return 1;
}

但是这么写很有可能TLE……

于是，证明又又又又又又又又又又来了……
$$ 其实，一个\sqrt x 就可以解决问题。\\\ why???\\\ （火车即将进入证明去，请大家扶稳坐好\\\ \\\ 设一个数x的其中一个约数为a，则：\\\ x \mod a \equiv 0\\\ x \div a必为整数。\\\ 不妨设x \div a = b，则:\\\ x \mod b \equiv 0\\\ a \times b = x\\\ \because 对与x的每一个约数a，都能找到这样的一个b。\\\ \therefore 因数成对出现\\\ 既然x的约数成对出现，判断质数时，我们不必枚举所有因数。\\\ 枚举到\sqrt x 即可。\\\ $$
优化后的代码：

int is_prime(int x)
{
    if(x == 1) return 0;
    if(x == 2) return 1;
    for(int i = 2; i <= sqrt(x); i ++)
    {
        if(x % i == 0) return 0;
    }
    return 1;
}

刚刚那道题的完整代码：

#include<iostream>
#include<cmath>
using namespace std;
int f(int x)
{
    if(x == 1) return 0;
    if(x == 2) return 1;
    for(int i = 2; i <= sqrt(x); i ++)
    {
        if(x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        if(f(x)) puts("Yes");
        else puts("No");
    }
}

埃氏筛质数。

首先，引入一个概念，什么叫筛质数。
其实很简单：

求1-n中的所有质数就是筛质数

这样的话我们需要把每个数都运行一遍判断质数，结果时间复杂度变成了：
$O(n\sqrt n)$
如果n = ${10} ^ 5$,
那运算次数就是：${10} ^ 5 \times 300$
大概是3000万次，基本要TLE，尤其要是限制再大一点，氧气臭氧都救不了你……

TLE*2
所以，数学巨佬们专门发明了几种方法筛质数，其中一个就是埃氏筛质数。
具体流程如下：

1. 开primes数组记录质数，st数组判断是否筛过，cnt记录数量。
2. 遍历2-n
3. 如果被筛过，coutinue
4. 否则标记
5. 最后把这个数的所有倍数筛掉
6. 愉快的结束了/bushi

然后就可以证明一下辣（愉快的证明又又又又又来了
$$ 首先，1不会进入循环。\\\ 接着设当前枚举的数是x，\\\ 首先我们证明，x是合数，x一定被筛过。\\\ 不妨设x \mod a \equiv 0, a != 1, a != x,a是质数。\\\ 如果质数不会被筛掉成立，合数被筛掉就一定成立。\\\ 接着我们尝试证明，x是质数，x没有被筛掉。\\\ 第一个枚举的数是2，\\\ 2是质数。\\\ 接下来这个证明有点类似递推的思想。\\\ 首先x如果是前面已经被筛过的数的倍数，则x \mod primes[i] \equiv 0,\\\ 那么x则不是质数。\\\ 那我们就把这个问题转化成了：如果x前面的数筛成，那就证毕。\\\ 不停的往前推，我们最开始已经证明了2是可以成立的，所以整个可以成立。\\\ $$

以上只是自己的证明，有错误请多多指正！！！

好我们来看一下埃氏筛质数的代码：

int n, primes[1000010], cnt, st[1000010];//数据范围感人
void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(st[i])continue;
        primes[cnt ++] = i;
        for(int j = i ; j <= n; j += i) st[j] = 1;
    }
}

接下来我们来看一下这道题

给定一个正整数n，请你求出1~n中质数的个数。

输入格式
共一行，包含整数n。

输出格式
共一行，包含一个整数，表示1~n中质数的个数。

数据范围
$ 1≤n≤{10}^6 $
输入样例：

8

输出样例：

4

这道题是让我们统计质数个数，我们直接输出cnt即可。
这里提供一份超短代码，天梯同学注意辣！！！！

#include<cstdio>
int n, primes[1000010], cnt, st[1000010];
void init(int n){
    for(int i = 2; i <= n; i ++){
        if(st[i])continue;
        primes[cnt ++] = i;
        for(int j = i ; j <= n; j += i) st[j] = 1;
    }
}
int main(){scanf("%d",&n);init(n);printf("%d",cnt);}

10行。

暴力求约数

众所周知，约数的特点就是：
$$ x \mod a \equiv 0 $$
所以根据这个特点，暴力！
使用暴力法的时间复杂度是：$O(n)$
不过暴力TLE，优化会管你，这种方法交会T飞……。
注意不是暴力出奇迹

TLE*3
不过那个是咱们下节课讲的，这里就不说了。
暴力的话就是写一个循环，从1-n枚举每个数。
如果这个数满足$x \mod i \equiv 0$,就把这个数放进res数组里。

for(int i = 1; i <= n; i ++)
{
    if(x % i == 0)
    {
        res[cnt ++] = i;
    }
}

最后要啥给啥。
比如看一下这个题

给定n个正整数ai，对于每个整数ai,请你按照从小到大的顺序输出它的所有约数。

输入格式
第一行包含整数n。

接下来n行，每行包含一个整数ai。

输出格式
输出共n行，其中第 i 行输出第 i 个整数ai的所有约数。

数据范围
$ 1≤n≤100, 2≤ai≤2∗{10}^9 $
输入样例：

2
6
8

输出样例：

1 2 3 6 
1 2 4 8 

这道题建议 处理
不过，该TLE还是TLE……
不过样例可以过，说明还是木有问题滴！

#include<iostream>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    while(n --)
    {
        long long int x;
        cin>>x;
        for(int i = 1; i <= x; i ++)
        {
            if(x % i ==0)
            {
                cout << i << ' ';
            }
        }
        cout << endl;
    }
}

我加点优化啊等一下。
事实证明，再多的优化也挡不住算法暴力程度。

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
using namespace std;
int main()
{
    long long int n;
    scanf("%lld", &n);
    while(n --)
    {
        long long int x;
        scanf("%lld", &x);
        for(int i = 1; i <= x; i ++)
        {
            if(x % i ==0)
            {
                printf("%d ", i);
            }
        }
        printf("\n");
    }
}

TLE*4
优化下一期给大家讲h。

费马小定理求逆元

以前我们已经讲过了快速幂，今天先来复习下。

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

今天来看一下怎么求 一个数的乘法逆元。

首先看一下什么是乘法逆元。

$$ 如果 a \equiv 0(\mod b)，希望把除法变成乘法。\\\ 找到一个数x，使得a \div b \equiv a \times x(\mod m)\\\ 我们把x叫做b\mod m的乘法逆元，\\\ a \div b \equiv a \times {b} ^ {-1}\\\ $$

那怎么求逆元呢？答案就是快速幂和费马小定理。
接下来是一段很复杂的东西。（来源于y总视频）
$$ 把等式两边同时\times b，\\\ b \times \frac a b \equiv b \times a \times {b} ^ {-1}\\\ a \equiv a \times b \times {b}^{-1}\\\ \because (b, m) = 1\\\ \therefore b \times {b} ^ {-1} \equiv 1 (\mod m)\\\ $$
所以说，其实逆元很弱，即：
$$ 找到一个x，使得b \times x \equiv 1 (\mod m)\\\ $$
然后我们今天讲m是质数的情况。
所以，我们把m改名为p。
接着，费马小定理就来了。
欢迎！！！。
接下来是实在记不住，只能给y总视频的。
$$ 若(a, n) = 1\\\ 则{a} ^ {φ(n)} \equiv 1(\mod n)\\\ 证明：（搬运y总）\\\ 假设1-n中与a互质的数为h_1,h_2,h_3 \cdots h_{φ(n)}\\\ 由于a和n是互质的，所以：\\\ a \times {h_1}, a \times {h_2}, a \times {h_3} \cdots a \times h_{φ(n)} 都与n互质。\\\ 接下来稍稍说一下为什么这里面两两不相同。\\\ 假设a \times {h_i} \equiv a \times {h_j}\\\ 有a \times {({h_i} - {h_j})} \equiv 0 (\mod n)\\\ 则{h_i} \equiv {h_j}\\\ 矛盾。\\\ 好继续.\\\ 因此{h_1},{h_2},{h_3}这组数和a\tiems{h_1},a\times{h_2},a\times{h_3}这组数的乘积一样。\\\ 则有：{a}^{φ(n)} \times {{h_1} \cdots {h_n}} \equiv 0(\mod n)\\\ {a}^{φ(n)} \equiv 1(\mod n)\\\ 这就是欧拉定理。\\\ 那你说好的费马小定理呢？不急 这是如果n是质数，则{a}^{φ(n)} \equiv 1(\mod n)\\\ 所以{a} ^ {p - 1} \equiv 1(\mod n)\\\ 这就是费马小定理。\\\ $$
那我们继续推怎么算乘法逆元。
$$ {b} ^ {p - 1} \equiv 1(\mod p)\\\ b \times {b} ^ {p - 2} \equiv (\mod p)\\\ 所以{b} ^ {p - 2} 就是乘法逆元。\\\ $$
所以，快速幂就可以快速的求出这个东西。
看一下这道题

给定n组ai,pi，其中pi是质数,求ai模pi的乘法逆元，若逆元不存在则输出impossible。

注意：请返回在0∼p−1之间的逆元。

乘法逆元的定义

若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b−1(mod m)。
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，bm−2即为b的乘法逆元。

输入格式
第一行包含整数n。

接下来n行，每行包含一个数组ai,pi，数据保证pi是质数。

输出格式
输出共n行，每组数据输出一个结果，每个结果占一行。

若ai模pi的乘法逆元存在，则输出一个整数，表示逆元，否则输出impossible。

数据范围
$ 1≤n≤{10}^5,\\\ 1≤ai,pi≤2∗{10}^9\\\ $
输入样例：

3
4 3
8 5
6 3

输出样例：

1
2
impossible

然后我们写一遍快速幂的板子再套一下费马小定理。

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

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

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, p;
        cin>> a>>p;
        if(a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}

好了今天的分享就到这里了。

这是我的全部分享

bye~