标签：数论基础 varphi times pmod ax 我们 equiv

数论：研究数与数之间的关系。如带余除法、因数倍数、同余整除等都是数论。

【筛法】

主要使用的筛法有两个：埃氏筛和欧拉筛（线性筛）。

使用筛法的原因很简单：对于一个数，我们要找它的因数不容易；但是对于一个因数，我们找它的倍数很简单。

【埃氏筛】

因为一个数的倍数一定不是质数，且任何数都能分解为若干质数之积，所以我们每找到一个质数，就把这个质数的所有倍数都标记为合数。

bool p[N] = {}; //p[i]=true表示i为质数
void shai() {
    p[0] = p[1] = false;
    for (int i = 2; i <= N; i++)
        p[i] = true;
    for (int i = 2; i <= N; i++)
        if (p[i]) {
            for (long long j = i; i * j <= N; j++) //删去所有倍数
                p[i * j] = false;
        }
}

注意：这里我们还有一个小优化，我们的 j 是从 i 开始枚举的，这是因为在 j < i 时，我们一定在 i 更小的时候就已经标记过 i * j 了。这样可以避免一些重复标记。

但是，我们发现埃氏筛依旧会出现重复标记的情况。例如 \(7\times 8=56\)，我们会在 \(i=7\) 的时候筛一遍 \(56\)，但是因为 \(8\) 有质因子 \(2\)，所以在 \(i=2\) 时也会筛一遍 \(56\)。

因为有重复标记，所以埃氏筛的时间复杂度略高于 \(O(n)\)。当 \(n\) 很大的时候，可以明显看出它和 \(O(n)\) 的差距。

【欧拉筛】

我们希望埃氏筛可以进化到 \(O(n)\) 的复杂度。

上面埃氏筛慢的原因，就在于一个数被多次标记。而多次标记的原因，是我们分类分的不好。
我们在上面把所有合数分类，这个分类的方法是 “如果 \(x\) 是质数 \(p\) 的倍数，我们就把 \(x\) 分入 \(p\) 的类中”。
并且，每找到一个质数，我们就把该质数对应的分类中所有的数都打上合数标记。

显然，这样的分类方法可能会让一个数被分入多个类中，从而导致多次标记。现在，我们需要一个新的分类方法，可以把所有合数无遗漏无重复的分类。

考虑一个合数 \(x\) 会被分进谁的类中。如果能把 \(x\) 分进它的一个因数的类中，我们就可以很方便地打标记。

既然我们要 \(x\) 的因数，不如直接取最简单的情况：把 \(x\) 分进它最大的真因数 \(x'\) 的类中。
因为 \(x'\) 是最大真因数，所以 \(x'\) 到 \(x\) 一定只差了一个质因子，并且是 \(x\) 的最小质因子 \(p\)。

因为 \(p\) 是 \(x\) 的最小质因子，所以 \(x'\) 的质因子一定都大于等于 \(p\)，于是我们可以枚举所有质数 \(a\)，满足 \(a\) 小于等于 \(x'\) 的最小质因子，并把 \(x' \times a\) 打上标记。因为 \(x'\) 的最小质因子都大于等于 \(a\)，所以这样可以保证 \(a\) 一定是 \(x'\times a\) 的最小质因数。

但是，对 \(x'\) 找最小质因子挺麻烦的。我们注意到这么一个性质：当 \(a\) 达到上限，也就是当 \(a=x'\) 的最小质因子时，\(a|x\)。因此，我们可以一直枚举 \(a\)，如果 \(a|x'\) 就退出循环。

因为每个数都会唯一地分进一个类中，故这个算法是 \(O(n)\) 的。

int prime[60000006], cnt = 0; //cnt记录当前质数个数
bool p[60000005] = {};

void init() {
    for (int i = 2; i <= n; i++) {
        if (!p[i])
            prime[++cnt] = i;
			
            //j <= cnt：只能枚举当前找出来的质数
        for (int j = 1; j <= cnt && prime[j] <= n / i; j++) {
            p[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

【运用线性筛思想解决问题】

分解质因数

对于一个数的分解质因数早已学过，但现在有了多次询问。

注意到，分解质因数的操作显然是一个可以递归的操作：如果要分解 \(x\)，\(x\) 的最小质因数是 \(p\)，那么相当于要分解 \(x/p\)，并且在 \(x\) 的分解中加上一个 \(p\)。

考虑记录 \(mn[x]\) 表示 \(x\) 的最小质因数。如果能求出所有数的 \(mn[]\)，我们就可以在 \(\log\) 的时间复杂度内回答一个询问。我们现在的任务就是预处理出 \(mn[]\) 数组。

还是一样的思路：对于一个数 \(x\)，求 \(mn[x]\) 很难，但是求出所有 \(mn[]=x\) 的很简单。

我们把每一个数都分进它最小质因数对应的类中。但是这样还是难以解决，所以我们考虑把每一个数都分进它最大真因数对应的类中。然后在枚举到一个数的最大真因数 \(i\) 时，枚举所有可能的最小质因数 \(prime[j]\)，并记录 \(mn[i\times prime[j]] = prime[j]\)。

可以发现，我们只需要在 p[i * prime[j]] = true 之后加上一句 mn[i * prime[j]] = prime[j] 即可。

因数个数与因数之和

因数个数的公式很简单：先分解质因数，然后每个质因数的指数加一再相乘。
但是，我们希望这个公式可以完成递推。

当我们已经知道了 \(n\) 的因数个数 \(f(n)\)，考虑乘上一个质数 \(p\) 后的 \(f(np)\) 会怎么变化。

\(n\) 中不含 \(p\)，那么 \(f(np) = (1+1)\times f(n)\)；
\(n\) 中含 \(p\)。因为我们的 \(p\) 实际上枚举到 \(n\) 的最小质因数就退出了，所以我们只需要考虑当 \(n\) 乘上了 \(n\) 的最小质因数后的变化。

我们只需要同时记录下 \(n\) 的最小质因数的次数 \(mn[n]\)，就可以方便地让 \(f(np)=f(n)\div(mn[n]+1)\times (mn[np] + 1)\)。（显然 \(mn[np]=mn[n]+1\)）

经过这么一系列的递推，我们就可以求出所有数的因数个数了。同理，因数和也可以求出来，只是公式不同而已。

【总结】

可以发现，我们在数论上的递推与动态规划时的递推并不相同。我们在数论上的递推通常不是由 \(k-1\) 推 \(k\)，而是由 \(k/...\) 推 \(k\)。而线性筛就给我们提供了一个很好的递推方法：枚举每一个数的最大真因数，然后乘上一个最小质因数进行递推。

【积性函数】

若 \(f(ab)=f(a)\times f(b)|(a,b)=1\)，称 \(f()\) 为积性函数。

例如上面的因数个数就是一个积性函数。

积性函数就意味着我们可以进行递推。

【欧拉函数】

定义 \(\varphi(n)\) 为 “小于 \(n\) 的数中与 \(n\) 互质的数的个数”。

若 \(n\) 的质因子为 \(p_1,p_2,...,p_k\)，则 \(\varphi(n)=n\times \displaystyle \prod^k_{i=1}\frac{p_i-1}{p_i}\)。

因此，我们可以这样求欧拉函数。

如果我们要求 \(1\sim n\) 的 \(\varphi()\)，肯定不能每一个都求一次。所以我们用上面欧拉筛的方法递推。

递推code

仪仗队

如果一个人位于 \((x,y)\)，要想被看到，必须 \((x,y)=1\)。
于是这个题就变成了问有多少对数互质。当然，我们考虑一半即可，注意对角线只有一个能看到，特殊处理。

考虑对于每一列 \(a\)，都要问比 \(a\) 小的有几个与 \(a\) 互质。所以答案就是 \(\varphi(1)+\varphi(2)+...+\varphi(n)\)。

【乘法逆元】

在题目中，我们经常需要取模。但是如果涉及除法，乱除可能导致答案错误。这时候，我们尝试用乘法在取模意义上代替除法。于是，乘法逆元诞生了。

若 \(ab \equiv 1 \pmod p\)，则记 \(a=b^{-1}=\frac{1}{b},b=a^{-1}=\frac{1}{a}\)，称 \(a,b\) 互为逆元。（模 \(p\) 意义下）

注意：只有 \(a,b\) 与 \(p\) 互质时才存在逆元。

逆元有什么用？如果我们要在模的意义下做除法，就相当于乘以除数的逆元。
那么如何快速求出逆元？

接下来我们做两件事。

若 \((a,p)=1\)，求证：\(a^{-1}\mod p\) 存在且唯一。
\(O(\log p)\) 的时间内求出 \(a^{-1}\mod p\)。

首先提出两个概念：完全剩余系和简化剩余系。

完全剩余系：简称完系。\(x\) 的完系为一个包含 \(x\) 个数的集合，满足集合中任何两个数模 \(x\) 的余数各不相同。

简化剩余系：简称简系。\(x\) 的简系为一个包含 \(\varphi(x)\) 个数的集合，满足集合中任何两个数模 \(x\) 的余数各不相同，且与 \(x\) 互质。

记 \(x\) 的完系为 \(R(x)\)，\(x\) 的简系为 \(R'(x)\)。

下证：若 \((a,p)=1\)，求证：\(a^{-1}\mod p\) 存在且唯一。

令 \(R'(p)=\{x_1,x_2,...,x_k\}\)。（\(k=\varphi(p)\)）

显然，因为 \((a,p)=1\)，所以 \(a\in R'(p)\)。如果 \(a^{-1}\) 存在，若 \((a^{-1},p)\neq 1\)，则 \(a\times a^{-1} \neq 1\)，矛盾。因此 \(a^{-1}\in R'(p)\)。

因为逆元就是相乘得一，所以我们考虑把所有东西都乘起来看看。

我们只需证明：对于任意 \(a\)，\((a,p)=1\)，则 \(ax_1,ax_2,...,ax_k\) 依然构成模 \(p\) 的简化剩余系。

\(ax_1,ax_2,...,ax_k\) 有 \(\varphi(p)\) 个。且由于 \((a,p)=(x_i,p) = 1\)，所以 \((ax_i, p)=1\)。
对于任意 \(i,j\)，\(ax_i \not\equiv ax_j \pmod p\)。这是因为 \(ax_i\equiv ax_j \pmod p \iff p\mid ax_i-ax_j \iff p\mid a(x_i-x_j)\iff p\mid x_i-x_j\)，矛盾。

因此，\(ax_1,ax_2,...,ax_k\) 也是模 \(p\) 的简系。显然简系中有一个 \(1\)。所以 \(x_1,x_2,...,x_k\) 中恰有一个是 \(a^{-1}\)。

证毕。

怎么求乘法逆元？

欧拉定理：对于 \((a,p) = 1\)，有 \(a^{\varphi(p)}\equiv 1 \pmod p\)。

证明：考虑模 \(p\) 的简化剩余系 \(x_1,x_2,...,x_k\)。由上面知 \(ax_1,ax_2,...,ax_k\) 也是简系。

所以 \(\displaystyle\prod^k_{i=1} x_i\equiv ax_1\times ax_2 \times ... \times ax_k \pmod p\)。

记 \(\displaystyle\prod^k_{i=1} x_i = X\)，则 \(X\equiv a^{\varphi(p)}X\pmod p\)。

又 \((X,p)=1,(a^{\varphi(p)},p)=1\)，所以 \(X,a^{\varphi(p)}\in R'(p)\)。

故，若 \(a^{\varphi(p)}\not\equiv 1\)，则 \(a^{\varphi(p)}X\not\equiv 1\cdot X\not\equiv X\)，矛盾。

所以 \(a^{\varphi(p)}\equiv 1\pmod p\)，证毕。

由于 \(a^{\varphi(p)}\equiv 1\pmod p\)，所以 \(a\times a^{\varphi(p)-1}\equiv 1\)，所以 \(a^{-1}=a^{\varphi(p)-1}\)。用快速幂求解即可。

【连续的乘法逆元】

连续乘法逆元

注意要求模数为质数。

如果对于每一个数，都用 \(a^{\varphi(p)-1}\) 算，就太慢了。

我们希望可以重复利用之前求出来的数据。

假设已知 \(1\sim (k-1)\) 的逆元，求 \(k\) 的逆元。\((\!\!\!\!\mod p)\)

考虑带余除法：\(p\div k=t\cdot\cdot\cdot\cdot\cdot\cdot \;r\;(0\leq r < k)\)

\(p=kt+r,kt+r\equiv 0 \pmod p\)。

两边同时乘 \(k^{-1}r^{-1}\)。利用逆元性质：相乘得一。

\(t\cdot r^{-1}+k^{-1}\equiv 0\pmod p\)。

\(k^{-1}\equiv -t\cdot r^{-1} \equiv -(p/k)\,(p \!\!\!\mod k)^{-1} \pmod p\)

所以，\(k^{-1}\) 可以用 \((p\,\%\,k)^{-1}\) 推出来。

初始设立 \(inv[1]=1\)，然后一路递推到 \(inv[n]\)。

带余除法：\(a\div p = t \dots\dots r\,(0\leq r<p)\)，\(a=pt+r\)。

如果我们想求 \(a\) 的某种属性，可以考虑用 \(p,t,r\) 三者的属性推出来。

【BSGS】

模板 BSGS

给定 \(b\)、\(p\)、\(n\)，求 \(l\) 使得 \(b^l \equiv n \pmod p\)

首先有一个枚举的想法，\(O(p)\)。

然后想到：

一个一个往前枚举太慢了，如果能先大幅度跨，然后再小幅度调整，时间就会快很多。

设 \(t=[\sqrt p],l=at+r(0\leq r < t)\)。

因为 \(l\) 显然 \(\leq p\)，\(t=[\sqrt p]\)，所以 \(a\) 的级别是 \(\sqrt p\)；因为 \(r<t\)，所以 \(r\) 的级别也是 \(\sqrt p\)。最终的复杂度是 \(O(\sqrt p)\) 的，是一个比较好的复杂度。

考虑用带余除法的方式转换式子。

\(b^l\equiv b^{at+r}\equiv (b^t)^a\times b^r \equiv n\pmod p\)。

我们枚举 \(a\)，考虑怎么求 \(r\)。当 \(a=a_0\) 时：

\((b^t)^{a_0}\times b^r\equiv n,b^r\equiv n\times [(b^t)^{a_0}]^{-1}\)。

如果我们能找到一个 \(r\) 满足 \(b^r\equiv n\times [(b^t)^{a_0}]^{-1}\)，那么这个 \(r\) 和 \(a_0\) 组成一组可行的解，然后就能直接通过 \(l=at+r\) 求出对应的 \(l\)。

但是，如果不能快速找到 \(r\)，时间并没有优化。那我们怎么快速找到 \(r\) ？

建立一个 map，索引时 \(n\times [(b^t)^{a_0}]^{-1}\)，键值是 \(r\)。这样当我们算出 \(n\times [(b^t)^{a_0}]^{-1}\) 时，我们可以立刻用 mp[\(\;n\times [(b^t)^{a_0}]^{-1}\;\)] 查询对应的 \(r\)。

【具体实现时的修改】

在具体实现时，我们让 \(l=at-r(1\leq r\leq t)\)。

\(b^l=b^{at-r}=(b^t)^a\div b^r\equiv n\)。

\(b^r\equiv (b^t)^a\times n^{-1}\)。

我们让 map[ \(b^r\) ] \(\rightarrow r\)，这样就可以用 map[ \((b^t)^a\times n^{-1}\) ] 快速求 \(r\)。

当然，我们也可以让 map[ \(b^r\times n\) ] \(\rightarrow r\)，这样我们的式子就应该是 \(b^r\times n \equiv (b^t)^a\)，调用 map[ \((b^t)^a\) ] \(\rightarrow r\) 进行查询。

至于 \(l=at-r\) 而非 \(l=at+r\) 的原因，是因为 \(map\) 里面查询不到会返回 0，如果 \(0\leq r < t\)，会混淆不存在和 \(r=0\)。

code

【裴蜀定理】

裴蜀定理

裴蜀定理：\(\displaystyle \sum_{i=1}^n A_ix_i = gcd(A_1,A_2,...,A_n)\) 一定有解。

二元形式：若 \((a,b)=1\)，则 \(ax+by=1\) 有解。

考虑模 \(b\) 的简系，这个简系乘 \(a\) 也是简系，其中必有一个 1。所以存在 \(ax=bk+1\)，此时令 \(y=-k\) 即可。

【拓展欧几里得算法】

【模板】二元一次方程组

判断无解：裴蜀定理，\(gcd(a,b)\) 是否整除 \(c\) 。

接下来尝试寻找一组整数解。一个简单的想法显然可以枚举 \(x\)，\(O(\min(a,b))\)。慢，考虑优化。

众所周知，辗转相除法可以求出 \(gcd(a,b)\)。那我们能否在辗转相除的过程中，顺便求出对应的解 \((x,y)\) 呢？

辗转相除法：不妨 \(a\geq b,gcd(a,b)=gcd(b,a\%b)\)。

对 \(ax+by=gcd(a,b)\) 的方程，考虑用辗转相除法递归：转化为 \(bx_0+(a\%b)y_0=gcd(b,a\%b)\)，用 \(x_0,y_0\) 推出 \(x,y\)。

这么做之所以好，是因为等式左侧的关系很明显，而右侧始终相等。

同样地，考虑辗转相除法的结束条件：\(a,b\) 中，一个是 0，另一个是最大公因数。
当我们递归结束时，方程变为 \(gcd(a,b)x_0+0\cdot y_0=gcd(a,b)\)。

显然此时的有解 \((1,0)\)。

现在我们希望通过这一层的解推出上一层的解。
即已知 \(bx+(a\%b)y=gcd(a,b)\) 有解 \((x_0,y_0)\)，求 \(ax+by=gcd(a,b)\) 的解 \((x,y)\)。

因为我们想要 \(b,a\%b\)，所以考虑把 \(a\) 拆掉，\(a=[\frac{a}{b}]\times b+a\%b\)。
现在的方程变为 \([[\frac{a}{b}]]\times b+(a\%b)]x+by=gcd(a,b)\)。

拆括号，\(b\cdot[\;[\frac{a}{b}]x+y\;]+(a\%b)x=gcd(a,b)\)。这不就是上一层的形式吗？

所以，令 \([\frac{a}{b}]x+y=x_0,x=y_0\) 即可。\((x,y)=(y_0,x_0-[\frac{a}{b}]y_0)\)。

【中国剩余定理】

中国剩余定理（孙子定理）

记 \(M=\displaystyle\prod^n_{i=1} p_i,M_i=M/p_i\)。显然 \((M,M_i)=1\)。

不妨设 \(M_i \;\rm mod\;p_i\) 逆元 \(M_i^{-1}\)。

有特解：\(x_0=\displaystyle\sum^n_{i=1} a_iM_iM_i^{-1}\)。

正确性：\(x_0 \equiv a_i\pmod {p_i}\) 吗？ \(x_0\) 中的 \(a_iM_iM_i^{-1}\) 贡献 \(a_i\) 的余数，其余项的 \(M_{()}\) 都包含 \(p_i\)，所以最终的余数就是 \(a_i\)。

通解：\(x=x_0+k\cdot M(k\in Z)\)。

【阶与原根】

阶：\(a\;\rm mod\;p\) 的阶为最小的 \(r\) 使得 \(a^r\equiv 1\pmod p\)。

性质一：若 \(a^k\equiv 1\pmod p\)，必有 \(r\mid k\)。

证明：若 \(r\mid\!\!\!\!\,\not \;\;k\)，记 \(k=tr+z(1\leq z<r)\)，则 \(a^z\equiv 1\pmod p\) 且 \(z<r\)，与 \(r\) 最小矛盾。

性质二：\(a^k\equiv a^{k-r}\pmod p\)。证明显然。

由于 \(a^{\varphi(p)}\equiv 1\pmod p\)，所以 \(r\mid \varphi(p)\)。

如果 \(r=\varphi(p)\)，称 \(r\) 为原根。

原根的性质：\(a^1\sim a^r\; \rm mod\;p\) 刚好构成一个 \(\rm mod\;p\) 的简系。

标签：数论,基础,varphi,times,pmod,ax,我们,equiv
From： https://www.cnblogs.com/FLY-lai/p/18016078

数论基础