Day 7:提高数论

Part1 基本

---

---

倍数与约数

倍数

对于$a, b$两个自然数，如果存在自然数$k$，使得$ka = b$那么b是a的倍数，称$a$ 整除 $b$，$b$能够被$a$整除，记作$a | b$

• 一个数有无穷多个倍数
• 所有数都是自身和$1$的倍数
• 倍数具有传递性
• 在$[1, n]$的范围内$x$的倍数有$\lfloor {n \over x} \rfloor$个

约数

• 对于自然数$a, b$，如果$b$ 是 $a$ 的倍数，那么$a$是$b$的约数
• 每个数的约数都包含自身和（或）$1$
• 每个自然数都只有有限个约数，$n$的约数个数通常记为$d(n)$

约数不会增长得很快，一般$10^9$内的数都最多$1000$多个约数。

//O(nlogn)打表d(n)
for(int i=1; i<=n; ++i)
    for(int j=i; j<=n; j+=i)
        d[j]++;

复杂度为什么是$O(nlogn)$？
时间复杂度是$O(n * (\Sigma_{i=1}^{n} {1 \over i}))$
括号内是调和级数，可以近似看成$ln(n)$

素数和唯一分解定理

素数与合数

• 如果一个数的约数只有$2$个（$1$和自身）那么称它是素数
• 如果一个数有非平凡约数（非$1$和自身）就是合数

注意，1不是素数，也不是合数

正常判断需要$O(\sqrt{n})$时间，代码就不写了。

埃氏筛法：$O(nloglogn)$

for(int i=2; i<=n; i++){
    if(!np[i]){
        p[++cnt] = i;
        for(int j=i+i; j<=n; j+=i)
            vis[j] = true;
    }
}

每个数被筛了很多次，所以可以进行优化。

欧拉筛法（线性筛）$O(n)$

for(int i=2; i<=n; ++i){
    if(!np[i]) p[++cnt] = i;
    for(int j=1; i * p[j]<=n; ++j){
        vis[i * p[j]] = true;
        //保证p[j] 是 i*p[j]的最小质因子
        if(i % p[j] == 0) break;
    }
}

每个数只会被最小的质因子筛一遍，所以筛出每个素数的时间是$O(1)$，所以时间复杂度是$O(n)$

但是埃氏筛法也有好处：可以区间筛，例如筛出$[10^9, 10^9+10^5]$区间内的素数。

估算素数的个数：$n \over \ln n$

唯一分解定理（算术基本定理)

• 每个大于1的自然数军可以写成素数的积，并且素因子按大小排列之后，写法仅有一种方式

• 乘法可以写成对应素因子的次数相加，除法可以写成对应素因子的次数相减。

• 如果一个数的每一个素因子的个数大于等于另一个数每一个对应素因子个数。

对唯一分解定理的证明

存在性

设一个自然数为$x$
1. 如果$x$是素数，那么显然只能写成它本身。
2. 如果$x$是合数，根据定义，它可以分解成几个数的积，递归证明即可

唯一性

设
$x = p1^m1 + p2^m2 + p3^m3 ... pn ^ mn$
$x = q1^t1 + q2^t2 + q3^t3 + ... qn^tn$
因为质数是不可以分解的，所以这两个表达式是等价的。

理解即可，详细的可以自行查阅

int factorize(int x, int p[]){ //每个数反复出现就会被记录多次
    int cnt = 0;
    for(int i=2; i*i<=x; i++){
        while(x % i == 0){
            p[++cnt] = i;
            x / = i;
        }
    }
    if(x > 1) p[++cnt] = x;
}

复杂度是$O(\sqrt{x} + \log_2x)$，因为sqrt较大，所以就是$O(\sqrt x)$

也可以在两个数组中记录质数和次数

linux中有factor命令，bash执行factor [INTEGER]，输入一个数就可以进行质因数分解，与上面的函数效果相同，十分方便。

gcd & lcm

最大公约数gcd

两个自然数共有的约数最大的一个，称为它们的最大公约数$(Greatest\quad Common\quad Divisor)$

利用唯一分解定理及推论，可以知道两个数的$gcd$就是两个数质因数分解后素因子次数取$min$后的数。

辗转相除法（欧几里得算法）

定义对于任何自然数$a$，$\gcd(0, a) = gcd(a, 0) = a$

则对于任意的自然数$a, b$，满足$gcd(a, b) = gcd(b, a \mod b)$

如果$p | a$ 且 $p | b$，那么$p|(b-a)$（辗转相减法），那么可以表示为$p | b\mod a$

int gcd_iter(int a, int b){
}
int gcd_recur(int a, int b){
    if(a == 0) return b;
    return gcd(b%a, a);
}

最小公倍数lcm

两个自然数共有的倍数最小的一个，成为它们的最小公倍数$(Least\quad Common\quad Multiple)$

可以发现lcm就是两个数对应的素因子个数取max的结果

不需要另外求，只需要用一个公式求：
$lcm(a,b) = {{ab} \over {\gcd(a, b)}}$

扩展欧几里得exgcd

定理：裴蜀定理

对于任意整数$a, b$，存在无穷多组整数对$(x, y)$满足不定方程$ax + by = d$，其中$d = gcd(a, b)$

在求$\gcd(a, b)$的同时，可以求出关于$x, y$的不定方程$ax+by=d$的一组整数解。

考虑递归计算：假如已经计算出了$\gcd(b\mod a, a)$的一组解，可以递推：
$(b - a \lfloor {b \over a} \rfloor )x_0 + ay_0 = d$$

可以整理得到递推代码，参见我的博客。以下是另外一种写法。

int exgcd(int a, int b, int &x, int &y){
    if(a == 0){
        x = 0; y = 1;
        return b;
    }
    //x = x0 - b/a*y0
    //y = y0
    int d = gcd(b%a, a, y, x);
    x -= b/a*y;
    return d;
}

Part1::Problems

P1403 约数研究

求$\Sigma^n_{i=1} d(i)$

1. 暴力统计$O(n \sqrt{n}) = O(TLE)$
2. 约数个数打表$O(nlogn)=O(卡过)$
3. 转化成倍数问题，套用倍数个数公式，$O(n) = O(AC)$

P1072 Hankson的趣味题

对于某个素数$p$，根据唯一分解定理及推论，对几个数进行质因数分解，得出每个质因数次数的取值范围，然后根据乘法原理取值。

可以用$O(\sqrt n)$枚举素因子，由于每个数至多只有一个大于$\sqrt n$的质因子，特判即可。$2000$组数据可以过。

可以先筛出素数，然后再质因数分解。

P2520 向量

设$d = \gcd(a,b)$，如果$x, y$不能整除$d$，显然无解，否则把$d$约掉。

可以把两部操作组合，组成新操作：以下$x$表示横坐标，$y$表示纵坐标

$$x += 2a$$ $$y += 2a$$

根据裴蜀定理，就可以得到$x+=2\quad y+=2$

考虑奇偶性，分别枚举起点：

$$(0,0)(a,b)(b,a)(a+b,a+b)$$

考虑这四种初始走法，然后可以用exgcd做。

Part2 提高

---

---

对于自然数$a$，正整数$m$，$a \mod m= a - \lfloor{a \over b} \rfloor \times b$

取模意义下的数和运算

如果$a \mod m = b \mod m$，可以记作$a \equiv b$

这样所有的自然数都能用$[1, m)$之间的整数代表。

取模可以拓展到负数，得数依然是小于$m$的非负整数。

可以建立一个新的数字运算体系，其中只有$[0,m)$的整数。

两个数相加，如果超过了$m-1$，就从$0$开始往上加，想乘与相加类似

Warning! C++中的负数取模与数学不完全相同，最好加成正数，在减法和一些数论题中注意

$(a+b) \mod m = (a \mod m + b \mod m) \mod m$
$(a-b) \mod m = (a \mod m - b \mod m + m) \mod m$ //防止负数取模，数学中可以不加m
$(a \times b) \mod m = (a \mod m \times b \mod m) \mod m$

除法不能保证可以除尽，所以在取模意义中较为麻烦

可以不断将除数加上$m$，直到可以除尽，但这样太慢了。

除以一个数可以转化为乘它的倒数。所以我们可以试着找一个乘法逆元，即满足$xx^{-1} = 1$的整数$x^{-1}$，$0$没有逆元。

当且仅当$m$为素数时，每个正整数都有唯一的乘法逆元，因此大部分OI题中模数都是素数。

费马小定理

对于任意的质数$p$和正整数$a<p$，都有$a^{p-1} \equiv 1(\mod p)$

易证$a,2a,3a...(p-1)a(\mod p)$可以取遍$[1,p)$之间的所有数。

反证法：假设这些数会出现重复。

那么一定有$k_1a \equiv k_2a$，那么$(k_1 - k_2)a \equiv 0$，不成立。

于是$a \times 2a \times 3a ... (p-1)a \equiv (p-1)!$

然后两边同时除以$(p-1)!$，得证。

欧拉定理（数论）

对于正整数$a<p$，则$a^{\phi p} \equiv 1(\mod p)$

有了费马小定理，可以快速求出乘法逆元

由于$a^{p-2} \times a \equiv a^{p-1} \equiv 1(\mod p)$，所以快速幂求$a^{p-2}$即可，$O(n \log n)$

也可以用$exgcd$求逆元，求解$ax + py = 1$ 即可。

中国剩余定理CRT

有若干个人列队，三个一排多$2$个，五个一排多$3$个，七个一排多$2$个，求人数至少是多少？

本质上是解一元线性同余方程组

$$x \mod a_1 = m_1$$
$$x \mod a_2 = m_2$$
$$...$$
$$x \mod a_n = m_n$$
当$m$两两互素时一定有解

尝试构造出这个解。

设$M = \Pi^{n}_{i=1} m_i,M_i = {M \over m_i}$

$M_i$只有在模$m_i$时不为零，模其他的$m$都为零我们想要在模$m_i$时得到$a_i$，所以需要乘上$a_it_i$，其中$t_i$是$M_i$在模$m_i$意义下的乘法逆元。

最终得到$a_1t_1M_1 + a_2t_2M_2 + ... +$，在对$M$取模，就得到了最小自然数解，加上$kM$就是通解。

为什么加起来就可以？

因为其他的模$m_i$就变成0了，只剩下当前这个

M太大怎么办？

...

Part2::Problems

P4079 齿轮

给定一个有向图，每条边代表连接的两个点上的数字需要满足某个比例，求是否有一种合法的方案给每个点分配一个数字。

• 可以用dfs或并查集做，依次分配数字。
• 但用int会溢出，用double会爆精度
• 可以考虑将所有数字对某个$P$取模，然后进行验证。

• 我们需要取多个$P$，分别做一遍，可以大几率通过。

• 也可以用取对数加减或质因数分解等奇怪方法做。

P2054 洗牌

• 把洗牌的过程反过来，会发现假设一张牌洗牌后是$x$，洗牌前是$2x \mod (n+1)$，证明较为复杂，需要用到置换矩阵。

• 解方程$2^mx \equiv l (\mod(n+1))$

求出$2^m$的逆元即可，由于$n+1$不一定是素数，所以求逆元只能用$exgcd$或欧拉函数