欧几里得算法
根据 \(\gcd(a,b)=\gcd(b,a\bmod b)\) 递归。
时间复杂度：\(O(\log n)\)。
证明：
- \(a<b\)，\(\gcd(a,b)=\gcd(b,a)\)，变为情况 2.
- \(a\geq b\)，\(\gcd(a,b)=\gcd(b,a\bmod b)\)，\(\Delta a=\left \lfloor \frac{a}{b} \right \rfloor\times b\)，考虑最劣的情况下，\(\Delta a\) 尽量小，即 \(\left \lfloor \frac{a}{b} \right \rfloor=1\)，所以 \(a<2b\)，\(\Delta a=b>\frac{a}{2}\)
所以每次 2 操作 \(a\) 至少减半，而 1 操作的次数不会超过 2，因此时间复杂度为 \(O(\log n)\)
注：用欧几里得算法求斐波那契数列相邻两项的 \(\gcd\) 会让该算法达到最坏复杂度。
扩展欧几里得算法
求 \(ax+by=\gcd(a,b)\) 的一组可行解。
设 \(ax_1+by_1=\gcd(a,b),bx_2+(a\bmod b)y_2=gcd(b,a\bmod b)\)，
有
\[\begin{aligned} ax_1+by_1 &=bx_2+(a\bmod b)y_2\\ &=bx_2+(a-\left\lfloor\frac{a}{b}\right\rfloor b)y_2\\ &=ay_2+b(x_2-\left\lfloor\frac{a}{b}\right\rfloor y_2)\\ \end{aligned} \]由上式可知：
\[\begin{cases} x_1=y_2 \\ y_1=x_2-\left\lfloor\frac{a}{b}\right\rfloor y_2 \end{cases} \]考虑欧几里得算法的终止条件，\(b=0\) 时，\(x_0=1,y_0=0\) 即是方程的一组特解，回溯即可求出 \(x,y\)。
裴蜀定理
-
定义：不定方程 \(ax+by=c\) 有整数解的充要条件是 \(\gcd(a,b)|c\)。
-
证明：
必要性：因为 \(\gcd(a,b)|(ax+by)\) ，又 \(ax+by=c\)，所以 \(\gcd(a,b)|c\)。
充分性：由上述过程可知，一定存在一组 \(x,y\) 使得 \(ax+by=\gcd(a,b)\)，所以当 \(\gcd(a,b)|c\) 时，\(ax+by=c\) 有整数解。
（感觉很口胡）
由裴蜀定理，我们可以用扩展欧几里得求出不定方程 \(ax+by=c\) 的整数解了。
欧拉函数
-
定义：\(\varphi(n)\) 表示小于等于 \(n\) 的正整数中与 \(n\) 互质的数的个数。
-
性质：
-
设 \(n=p_1^{c_1}p_2^{c_2}...p_m^{c^m}\) ，则 \(\varphi(n)=n\prod\limits_{i=1}^m \frac{p_i-1}{p_i}\)。
证明：容斥，再归纳一下。
-
\(n=\sum\limits_{d|n} \varphi(d)\)
证明：
\(n =\sum\limits_{i|n}\sum\limits_{j=1}^{n}[\gcd(j,n)=i]\)
令 \(f(i)=\sum\limits_{j=1}^n[\gcd(j,n)=i]=\sum\limits_{j=1}^\frac{n}{i}[\gcd(j,\frac{n}{i})=1]\)
即 \(f(i)=\varphi(\frac{n}{i})=\varphi(i)\)
因此 \(n=\sum\limits_{d|n} \varphi(d)\)
-
欧拉函数是积性函数。
费马小定理
-
前置——同余性质（在接下来的证明中可能会多次使用）：
- 传递性
- 如果 \(x\equiv y\pmod p\)，则存在 \(k\in \mathbb Z\) 使得 \(x=kp+y\)。
- 如果 \(x\equiv y\pmod p\)，则对于任意 \(k\) 有 \(kx\equiv ky\pmod p\)，\(x+k\equiv y+k\pmod p\)，\(x-k\equiv y-k\pmod p\)。
- 如果 \(a\equiv b\pmod p\)，\(c\equiv d\pmod p\)，则 \(ac\equiv bd\pmod p\)。
-
定义：对于质数 \(p\)，若 \(\gcd(a,p)=1\)，有 \(a^{p-1}\equiv 1\pmod p\)。
-
证明：
考虑通过证明 \(\prod\limits_{i=1}^{p-1} i\equiv \prod\limits_{i=1}^{p-1}(ia \bmod p)\) 证明费马小定理。
假设存在 \(1\leq x<y\leq p-1\)，满足 \(ax\equiv ay \pmod p\)。
则 \(a(y-x)\equiv 0 \pmod p\)
因为 \(a,y-x\) 均与 \(p\) 互质，所以上式不成立，所以 \(a \bmod p,2a\bmod p,...,(p-1)a\bmod p\) 两两不同，\(\prod\limits_{i=1}^{p-1} i\equiv \prod\limits_{i=1}^{p-1}(ia \bmod p)\) 。
所以 \((p-1)!\equiv a^{p-1}(p-1)!\pmod p\Rightarrow a^{p-1}\equiv 1\pmod p\) 。
欧拉定理
-
定义：对于 \(a,n\in \mathbb{Z^+}\)，且 \(\gcd(a,n)=1\)，有 \(a^{\varphi(n)} \equiv 1 \pmod n\)。
-
证明：
与费马小定理类似，设 \(S=\{x|x\leq n,\gcd(x,n)=1\}\)，\(|S|=\varphi(n)\)
通过证明 \(\prod\limits_{i=1}^{\varphi(n)}x_i\equiv \prod\limits_{i=1}^{\varphi(n)} (x_i a\bmod n)\) 证明欧拉定理。
假设存在 \(1\leq i<j\leq \varphi(n)\)，满足 \(ax_i\equiv ax_j\pmod n\)。
则 \(a(x_j-x_i)\equiv 0\pmod n\)，
因为 \(a\) 与 \(n\) 互质，且 \(0<x_j-x_i<n\)，假设不成立。所以 \(ax_i\bmod n\) 两两不同，\(\prod\limits_{i=1}^{\varphi(n)}x_i\equiv \prod\limits_{i=1}^{\varphi(n)} (x_i a\bmod n)\)。
所以 \(\prod\limits_{i=1}^{\varphi(n)}x_i\equiv a^{\varphi(n)}\prod\limits_{i=1}^{\varphi(n)} x_i\pmod n\Rightarrow a^{\varphi(n)}\equiv1\pmod n\)。
-
另一种形式：\(a^b\equiv a^{b\bmod \varphi(n)}\pmod n\)。
证明：读者自证不难（。
扩展欧拉定理
-
定义：对于 \(a,k,n\in \mathbb Z^+\)，\(k\geq\varphi(n)\)，有 \(a^k\equiv a^{k\bmod \varphi(n)+\varphi(n)}\pmod n\)。
-
证明：
引理:
- 整数 \(a,b,n,m\)，满足 \(a=a'm,b=b'm,n=n'm,a\equiv b \pmod n\)，则 \(a'\equiv b'\pmod {n'}\)。
- 整数 \(a,b,n\)，满足 \(a\equiv b\pmod n,k\ne 0\)，则 \(ak\equiv bk\pmod {nk}\)
设 \(a=p_1^{b_1}p_2^{b_2}...p_n^{b_n}\)，要证 \(a^k\equiv a^{k\bmod \varphi(n)+\varphi(n)}\pmod n\)，只需证 \(p_i^k\equiv p_i^{k\bmod \varphi(n)+\varphi(n)}\pmod n\)。按 \(p_i\) 是否是 \(n\) 的质因子讨论。不是的话显然，这里只讨论是的情况。设 \(n=p_1^{c_1}p_2^{c_2}...p_n^{c_n}\) ，记 \(m=\frac{n}{p_i^{c_i}}\)。
设 \(p_i^k\equiv d \pmod n\)，则
\[p_i^k=tn+d=tmp_i^{c_i}+d \]因此 \(p_i^{c_i}|d\)，由引理 1 两边同除 \(p_i^{c_i}\) 得，
\[p_i^{k-c_i}\equiv\frac{d}{p_i^{c_i}}\pmod m \]又 \(\gcd(p_i,m)=1\)，由欧拉定理，
\[p_i^{\varphi(m)}\equiv 1\pmod m \]因为欧拉函数是积性函数，所以 \(\varphi(n)=\varphi(p_i^{c_i})\varphi(m)\)，所以
\[p_i^{\varphi(n)}\equiv 1\pmod m \]由欧拉定理，
\[\begin{aligned} p_i^{k-c_i}&\equiv p_i^{(k-c_i)\bmod \varphi(n)}\\ &\equiv p_i^{(k-c_i)\bmod\varphi(n)+\varphi(n)}\\ &\equiv \frac{d}{p_i^{c_i}}\pmod m \end{aligned} \]由引理 2，
因为第二三项的指数中有一个等于 \(k\bmod \varphi(n)+\varphi(n)\)，所以
\[ p_i^k\equiv p^{k\bmod\varphi(n)+\varphi(n)}\pmod n \]完结撒花！
- 费马小定理，欧拉定理，扩展欧拉定理主要用于降次，比如有毒瘤出题人把指数搞成高精度数。
线性求逆
- 根据如下递推式求解：
- 证明\((a>1)\)：
因为 \(p=\left\lfloor \frac{p}{a}\right\rfloor a+(p\bmod a)\)
\[\left\lfloor \frac{p}{a}\right\rfloor a+(p\bmod a)\equiv 0\pmod p \] 两边同乘 \(a^{-1}(p\bmod a)^{-1}\) 得，
\[a^{-1}+\left\lfloor\frac{p}{a}\right\rfloor(p\bmod a)^{-1}\equiv 0\pmod p\\ a^{-1}\equiv -\left\lfloor\frac{p}{a}\right\rfloor(p\bmod a)^{-1}\equiv (p-\left\lfloor\frac{p}{a}\right\rfloor)(p\bmod a)^{-1}\pmod p \]素性测试
这里说的是概率性测试，即有概率将合数判断为质数。
Fermat 素性测试
核心是利用费马小定理，我们知道对于质数 \(p\)，若 \(\gcd(a,p)=1\)，有 \(a^{p-1}\equiv 1\pmod p\)。
基本思想是在 \([2,p-1]\) 中随机 \(a\)，判断是否有 \(a^{p-1}\equiv 1\pmod p\)。
卡迈克尔数：如果合数 \(n\)，满足所有与 \(n\) 互质的正整数 \(a\) 都有 \(a^{n-1}\equiv 1 \pmod n\)，则称合数 \(n\) 为卡迈克尔数。
Miller-Rabin 素性测试
Fermat 素性测试的加强版。
-
二次探测定理：对于质数 \(p\)，如果 \(x^2\equiv 1\pmod p\)，则 \(x\equiv \pm 1\pmod p\)
证明：平方差公式。
-
实现：
将 \(p-1\) 分解为 \(2^k\times t\) 的形式。如果 \(p\) 是质数，那么 \(a^{2^k\times t}\equiv 1\pmod p\)。
我们每次随机 \(a\)，算出 \(a^t\)，记为 \(A\)。
循环 \(k\) 次，每次判断是否 \(A^2\equiv 1\pmod p\) 且 \(A\equiv \pm 1\pmod p\)。如果不满足则 \(p\) 不是质数。否则令 \(A\leftarrow A^2\)
\(k\) 次后判断 \(A\equiv 1\pmod p\) 是否成立，如果成立，则认为 \(p\) 是质数。
-
Code：
bool miller(ll x) { if(x==1) return 0; ll p=x-1,k=0; while(!(p&1)) p>>=1,k++; for(int i=1;i<=9;i++) { if(x==a[i]) return 1; A=qpow(a[i],p,x); ll nxt=A; for(int j=1;j<=k;j++,A=nxt) { nxt=A*A%x; if(nxt==1&&A!=1&&A!=x-1) return 0; } if(A%x!=1) return 0; } return 1; }
线性同余方程
\(ax\equiv b\pmod n \Leftrightarrow ax+ny=b\)
用扩展欧几里得求解即可。
中国剩余定理
-
定义：方程组（\(m_i\) 两两互质）：
\[\begin{cases} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \cdots\\ x\equiv a_n\pmod {m_n} \end{cases} \]有整数解，且在模 \(M=\prod_{i=1}^n m_i\) 意义下有唯一解。
令 \(M_i=\frac{M}{m_i}\)，\(M_i^{-1}\) 为 \(M_i\) 在模 \(m_i\) 意义下的逆元，则
\[x=\sum\limits_{i=1}^n M_iM_i^{-1}a_i\pmod M \] -
证明：
将 \(x\) 代入第 \(k\) 个方程得，
\[\begin{aligned} \sum\limits_{i=1,i\ne k}^n M_iM_i^{-1}a_i+M_kM_k^{-1}a_k&\equiv a_k\pmod {m_k}\\ \sum\limits_{i=1,i\ne k}^n M_iM_i^{-1}a_i&\equiv 0\pmod {m_k} \end{aligned} \]因为 \(M_i=\frac{M}{m_i}\)，所以对于任意 \(i\ne k\)，\(m_k|M_i\)，上式成立。
扩展中国剩余定理
\(m_i\) 不互质。
假设只有两个方程：
\[\begin{cases} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2} \end{cases} \]可以转化为： \(x=a_1+k_1m_1,x=a_2+k_2m_2\)，即 \(k_1m_1-k_2m_2=a_2-a_1\)。
当 \(\gcd(m_1,m_2)|a_2-a_1\) 时不定方程有解，算出 \(k_1\)，则 \(x\equiv a_1+k_1m_1\pmod {\operatorname{lcm}(m_1,m_2)}\)。
多个方程同理。
BSGS 算法
求解 \(a^x\equiv b\pmod p\)，满足 \(\gcd(a,p)=1\)。
令 \(t=\sqrt p\)，设 \(x=it-j(0\leq j<t)\)，则 \(a^{it}\equiv ba^j\pmod p\)。
预处理出 \(ba^j\bmod p\) 的值，枚举 \(i\)，二分查找是否存在 \(ba^j\bmod p=a^{it}\bmod p\)。如果存在即找到一组解，且为最小整数解。
扩展 BSGS 算法
\(\gcd(a,p)\ne 1\) 的情况。
\(a^x\equiv b\pmod p\Leftrightarrow a^x+kp=b\)，若 \(\gcd(a,p)\nmid b\) 则无解。
两边同除 \(\gcd(a,p)\) 得，
\[\frac{a}{\gcd(a,p)}a^{x-1}+k\frac{p}{\gcd(a,p)}=\frac{b}{\gcd(a,p)} \]令 \(p_1=\frac{p}{\gcd(a,p)},b_1=\frac{b}{\gcd(a,p)}\)，
若 \(\gcd(a,p_t)\nmid b_t\) 则无解，若 \(\frac{a}{\gcd(a,p_t)}=b_{t+1}\) 则得到解 \(x=t+1\)，（\(t+1\) 即为经过几轮操作），否则重复上述过程。
若存在 \(t\) 使 \(\gcd(a,p_t)=1\)，则方程可化为
\[\frac{a^t}{\gcd(a,p)...\gcd(a,p_{t-1})}a^{x-t}+kp_t=b_t \]用 BSGS 算法解
\[a^{x-t}\equiv b_t(\frac{a^t}{\gcd(a,p)...\gcd(a,p_{t-1})})^{-1}\pmod {p_t} \]即可。
卢卡斯定理
-
定义：若 \(p\) 为质数，则
\[\dbinom{n}{m}\equiv\dbinom{\left\lfloor n/p\right\rfloor}{\left\lfloor m/p\right\rfloor}\dbinom{n\bmod p}{m\bmod p}\pmod p \]
扩展卢卡斯定理
\(p\) 不为质数的情况。
基本思路是将 \(p\) 分解为 \(p_1^{c_1}p_2^{c_2}...p_n^{c_n}\)，分别计算出 \(a_i=\dbinom{n}{m}\bmod p_i^{c_i}\)，再用中国剩余定理合并。
接下来考虑如何求 \(a_i\)，
\[\frac{n!}{m!(n-m)!}\bmod p^c \]直接算逆元显然是不行的，因为不一定互质，那么我们想让他们互质怎么办呢？
\[\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\frac{(n-m)!}{p^z}}p^{x-y-z}\bmod p^c \]\(x,y,z\) 分别为 \(n!,m!,(n-m)!\) 中 \(p\) 的个数。
问题转化为求 \(\frac{n!}{p^x} \bmod p^c\)。
\[\begin{aligned} n!&=1\times2\times...\times n\\ &=(p\times2p...\left\lfloor\frac{n}{p}\right\rfloor p)(1\times2\times...\times n)\\ &=p^{\left\lfloor\frac{n}{p}\right\rfloor}(\left\lfloor\frac{n}{p}\right\rfloor)!\prod\limits_{i=1,i\bmod p\ne 0}^n i\\ \end{aligned} \]最后这坨 \(\bmod p^c\) 是有循环节的，
\[\begin{aligned} &=p^{\left\lfloor\frac{n}{p}\right\rfloor}(\left\lfloor\frac{n}{p}\right\rfloor)!(\prod\limits_{i=1,i\bmod p\ne 0}^{p^c}i)^{\left\lfloor\frac{n}{p^c}\right\rfloor}(\prod\limits_{i=p^c\left\lfloor\frac{n}{p^c}\right\rfloor,i\bmod p\ne 0}^n i)\\ \end{aligned} \]举个栗子：
\[\begin{aligned} 18!&\equiv (1\times2\times4\times5\times7\times 8)\times(10\times 11\times13\times14\times16\times17)\times(3\times 6\times9\times 12\times 15)\pmod {3^2}\\ &\equiv 3^5\times 5!\times(1\times2\times 4\times 5\times 7\times 8)^2\pmod {3^2} \end{aligned} \]设 \(f(n)=\frac{n!}{p^x},g(n)=x\)，则
\[f(n)=f(\left\lfloor\frac{n}{p}\right\rfloor)(\prod\limits_{i=1,i\bmod p\ne 0}^{p^c}i)^{\left\lfloor\frac{n}{p^c}\right\rfloor}(\prod\limits_{i=p^c\left\lfloor\frac{n}{p^c}\right\rfloor,i\bmod p\ne 0}^n i)\\ g(n)=\left\lfloor\frac{n}{p}\right\rfloor+g(\left\lfloor\frac{n}{p}\right\rfloor) \]Pollard Rho 算法
请读者自行了解 博客
前置芝士：
-
Miller-Robin 素性测试
-
生日悖论：了解一下就行。\(n\) 个人中有两个人生日相同的概率，发现当 \(n=60\) 时，这个概率就很大了。经计算，在值域为 \(k\) 时，该问题在 \(\sqrt k\) 时概率就很大了。
-
Floyd 找环：
脑补一个 \(\rho\) 形的图，现在有两个人同时从尾端出发，\(v_1=1,v_2=2\) ，两人最终会在环上相遇。
算法流程：
对于合数 \(n\) ，一定存在 \(m\leq \sqrt n\) 且 \(m\) 是非平凡的，\(\gcd(x,n)=m\)。
我们构造一个伪随机函数 \(f(x)=(x^2+c)\bmod n\)，随机 \(x_1,c\) ，令 \(x_i=f(x_{i-1})\)，如果 \(x_i\) 重复出现，那么必然成环，根据生日悖论，这个概率在元素数到 \(\sqrt n\) 时就很大了。 所以 \(x\) 序列形如 \(\rho\)，尾长和环长的期望为 \(\sqrt n\)。
现在假设我们又构造了一个序列 \(y\)，\(y_i=x_i\bmod m\)，同上尾长和环长的期望为 \(\sqrt m\)。如果存在 \(x_i\ne x_j,y_i=y_j\)，即 \(m||x_i-x_j|\)，这时我们就找到了一个 \(n\) 的因数 \(\gcd(|x_i-x_j|,n)\) 。
考虑如何求 \(x_i,x_j\)，用两个指针 \(i,j\)，\(i=2j\)，每次求一下 \(\gcd(|x_i-x_j|,n)\)，如果 \(\ne 1\) 证明找到了，如果 \(x_i=x_j\) 则换一下 \(c\) 或者 \(x_1\)。
这样我们得到一个 \(O(n^{\frac{1}{4}}\log A)\) （\(A\) 是值域）的算法。
再来考虑如何优化掉这个 \(\log A\)。因为 \(\gcd(x,n)>1\)，则 \(\gcd(\prod x,n)>1\)。所以我们一块一块的求 \(\gcd\)，块长一次为 \(1,2,4...\)。这样就优化为 \(O(\log(n^{\frac{1}{4}})\log A+n^{\frac{1}{4}})\)，\(\log(n^{\frac{1}{4}})\) 可以忽略，也就是 \(O(n^{\frac{1}{4}}+\log A)\)。
Code：
ll pollard(ll n) {
if(n==4) return 2;
ll x1=(rand()%n+n)%n,c=((rand()%n+n)%n*(rand()%n+n)%n)%n;
x1=f(x1,n,c);
ll x2=f(x1,n,c);
int len=1;
ll tmp;
while(x1!=x2) {
ll mul=1;
for(int i=1;i<=len&&x1!=x2;i++) {
if(!(mul*(labs(x2-x1))%n))
return gcd(mul,n);
mul=mul*labs(x2-x1)%n;
x1=f(x1,n,c),x2=f(f(x2,n,c),n,c);
}
tmp=gcd(mul,n);
if(tmp>1) return tmp;
if(len<128) len<<=1;
}
return pollard(n);
}
莫比乌斯反演
前置芝士：
-
数论分块：当可以 \(O(1)\) 计算 \(f(r)-f(l)\) 或可以预处理 \(f\) 的前缀和时，数论分块就可以在 \(O(\sqrt n)\) 的时间内计算形如 \(\sum_{i=1}^nf(i)g(\left\lfloor\frac{n}{i}\right\rfloor)\) 的和式。
结论：对于常数 \(n\)，使得式子
\[\left\lfloor\frac {n}{i}\right\rfloor=\left\lfloor\frac {n}{j}\right\rfloor \]成立的最大的满足 \(i\leq j\leq n\) 的 \(j\) 的值为 \(\left\lfloor\dfrac {n}{\lfloor\frac ni\rfloor}\right\rfloor\)。即值 \(\left\lfloor\dfrac ni\right\rfloor\) 所在的块的右端点为\(\left\lfloor\dfrac {n}{\lfloor\frac ni\rfloor}\right\rfloor\)。
莫比乌斯函数：
- 定义：
-
莫比乌斯反演：
\[\sum\limits_{d|n}\mu(n)= \begin{cases} 1 &n=1\\ 0 &n\ne 1 \end{cases} \]用得多的还是变式：
\[\sum\limits_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1] \] -
一些式子的推：
筛法
前置
-
狄利克雷卷积
设 \(f,g\) 为两个数论函数，他们的狄利克雷卷积也是一个数论函数，其定义为：
\[h(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d}) \] -
常见数论函数及关系：
\(I(x)=1\)
\(id(x)=x\)
\(\varepsilon(x)=[x=1]\)
\(d(x)\) 约数个数
\(\sigma(x)\) 约数和
\(\varphi(x)\) 欧拉函数
\(\mu(x)\) 莫比乌斯函数
\(\mu*I=\varepsilon\)
\(\varphi*I=id\)
杜教筛
常用来在低于线性的时间内求解数论函数的前缀和。
对于数论函数 \(f\)，要求 \(S(n)=\sum_{i=1}^nf(i)\)。
我们构造一个函数 \(g\)，求出 \(h=f*g\)，则有
\[\begin{aligned} \sum\limits_{i=1}^nh(i)=\sum\limits_{i=1}^n\sum\limits_{d|i} g(d)f(\frac{i}{d})=\sum\limits_{d=1}^n g(d)s(\left\lfloor\frac{n}{d}\right\rfloor) \end{aligned} \]提出 \(d=1\) 的这一项得：
\[g(1)s(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)s(\left\lfloor\frac{n}{d}\right\rfloor) \]可以发现，杜教筛要求能快速求解 \(g\) 和 \(h\) 的前缀和。
复杂度 \(O(n^{\frac{2}{3}})\) （不会证）。
Min_25 筛
在低于线性的时间内求解积性函数的前缀和。
对于积性函数 \(f\)，要求 \(S(n)=\sum_{i=1}^n f(i)\)。
首先构造一个完全积性函数 \(F\)，满足在质数处取值与 \(f\) 相等，且能快速求前缀和。
先考虑求质数的贡献。设 \(G(n,i)\) 表示 \(2-n\) 中所有质数和最小质因子大于 \(p_i\) 的数的 \(F\) 之和。考虑转移，每次减去最小质因子等于 \(p_i\) 的合数的贡献，因此转移如下：
\[G(n,i)= \begin{cases} G(n,i-1) &p_i^2>n\\ G(n,i-1)-F(p_i)(G(\left\lfloor\frac{n}{p_i}\right\rfloor,i-1)-G(p_i-1,i-1)) &p_i^2\leq n \end{cases} \]所有质数的贡献即 \(G(n,cnt)\)，\(cnt\) 表示小于等于 \(n\) 的质数个数。
接下来考虑求所有数的贡献。设 \(S(n,i)\) 表示 \(2-n\) 中所有最小质因子大于 \(p_i\) 的数的 \(f\) 之和。质数部分可以通过 \(G\) 求得，现在考虑合数部分。我们枚举最小质因子和最小质因子的指数 \(p_k^e\)。然后当 \(e\ne1\) 时，\(p_k^e\) 也是一个合数，要把贡献算上。
\[S(n,i)= \begin{cases} \sum\limits_{j=i+1}^{cnt}f(p_j) &p_j^2>n\\ \sum\limits_{j=i+1}^{cnt}f(p_j)+\sum\limits_{k=i+1}^{cnt}\sum\limits_{e,p_k^e\leq n}f(p_k^e)(S(\left\lfloor\frac{n}{p_k^e}\right\rfloor,k)+[e\ne 1]) &p_j^2\leq n \end{cases} \]Problem：
Code：
可以看看码再理解理解。
//s1,s2为质数处的前缀和
void init() {
ll j,x;
for(ll i=1;i<=n;i=j+1) {
x=n/i,j=n/x;
val[++tot]=x;
if(x<=m) id1[x]=tot;
else id2[j]=tot;
x%=mod;
g1[tot]=(1LL*x*(x+1)%mod*inv2%mod*(2*x+1)%mod*inv3%mod-1+mod)%mod;
g2[tot]=(1LL*(x+1)*x%mod*inv2%mod-1+mod)%mod;
}
}
void getg() {
for(int i=1;i<=cnt;i++) {
for(int j=1;j<=tot&&p[i]*p[i]<=val[j];j++) {
int nw=ID(val[j]/p[i]);
g1[j]=(g1[j]-p[i]*p[i]%mod*((g1[nw]-s1[i-1]+mod)%mod)%mod+mod)%mod;
g2[j]=(g2[j]-p[i]*((g2[nw]-s2[i-1]+mod)%mod)%mod)%mod;
}
}
}
ll getS(ll x,ll y) {
if(p[y]>x) return 0;
int nw=ID(x);
ll ans=((g1[nw]-g2[nw]+mod)%mod-(s1[y]-s2[y]+mod)%mod+mod)%mod;
for(int i=y+1;i<=cnt&&p[i]*p[i]<=x;i++) {
ll tmp=p[i];
for(int j=1;tmp<=x;j++,tmp*=p[i]) {
ans=(ans+tmp%mod*((tmp-1+mod)%mod)%mod*(getS(x/tmp,i)+(j!=1))%mod)%mod;
}
}
return ans;
}
复杂度：\(O(玄学)\)。
目前只会对 \(25\) 取 \(\min\) 的做法。
Powerful Number 筛（附）
-
Powerful Number（PN）
-
定义：对于正整数 \(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)，若任意 \(1\leq i\leq m\)，都有 \(c_i>1\)，则称 \(n\) 为Powerful Number。
-
性质：
-
所有 PN 都可以表示成 \(a^2b^3\) 的形式。
证明：若 \(c_i\) 为偶数合并到 \(a^2\)，否则先将 \(p_i^3\) 合并到 \(b^3\)，再将 \(p_i^{c_i-3}\) 合并到 \(a^2\)。
-
\(n\) 以内至多 \(O(\sqrt n)\) 个 PN。
证明：不会。
-
-
求解：筛出 \(\sqrt n\) 内的质数，再 DFS，复杂度 \(O(\sqrt n)\)。
-
-
PN 筛
在低于线性的时间内求解积性函数的前缀和。
首先构造积性函数 \(g\)，满足在质数处取值与 \(f\) 相等，且能快速求前缀和。
然后构造函数 \(h\)，满足 \(f=g*h\)，可知 \(h\) 为积性函数，则 \(h(1)=1\)。
下面证明 \(h\) 在非 PN 数处取值为 \(0\)：
\(\because f(p)=g(1)h(p)+g(p)h(1),g(p)=f(p)h(1),g(p)=f(p),h(1)=1\)
\(\therefore h(p)=0\)
又 \(\because h\) 为积性函数
\(\therefore\) \(h\) 在非 PN 数处取值为零。
根据 \(f=g*h\)，有
\[\begin{aligned} S(n)&=\sum\limits_{i=1}^n f(i)\\ &=\sum\limits_{i=1}^n\sum\limits_{d|i} h(d)g(\left\lfloor\frac{i}{d}\right\rfloor)\\ &=\sum\limits_{d=1}^n h(d)G(\left\lfloor\frac{n}{d}\right\rfloor)\\ &=\sum\limits_{d=1,d\text{ is PN}}^n h(d)G(\left\lfloor\frac{n}{d}\right\rfloor) \end{aligned} \]我们可以算出所有 \(h(p^c)\) 的值，然后推出所有 \(h(d)\) 的值。
关于计算 \(h(p^c)\) 可以硬推式子，或者根据
\[f(p^c)=\sum\limits_{i=0}^c g(p^i)h(p^{c-i}) \]移项得
\[h(p^c)=f(p^c)-\sum\limits_{i=1}^c g(p^i)h(p^{c-i}) \]
杂
注：若无特殊说明，以下质数均为正数。
一个之前不知道的性质：
所有大于 \(3\) 的质数都可以表示为 \(6n\pm1\) 的形式1。（反之不成立！）
证明：
假设把质数都写成 \(n=6q+r\) 的形式，\((q\geq 0,r=0,1,2,3,4,5)\)。
\(r=0\) 时，\(6|n\)。\(r=2,4\) 时，\(2|n\)。\(r=3\) 时，\(3|n\)。均不可能为质数。
\(r=1\) 时，\(n=6q+1\)
\(r=5\) 时，\(n=6(q+1)-1 \Leftrightarrow n=6q-1\)
证毕。
质数计数函数：
小于等于 \(x\) 的质数数量，记为 \(\pi(x)\)，随着 \(x\) 增大，有近似 \(\pi(x)\sim\frac{x}{\ln(x)}\)。
反素数：
-
定义：对于任何正整数 \(x\)，其约数的个数记作 \(f(x)\)。如果某个正整数 \(x\) 满足：\(\forall 0 \lt i \lt x\)，都有 \(f(x) > f(i)\)，则称 \(x\) 为反素数。
可以理解为：约数最多（如果约数个数相同，值最小）。
注：注意区分 emirp，字面意思。
-
性质：
-
反素数一定时从 \(2\) 开始连续质数次幂乘积的形式。
证明：若不连续，在次数不变的情况下我们可以用一个更小的质数来替换较大的质数。
-
反素数 \(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m},(p_1>p_2...>p_m)\)，则 \(c_1\geq c_2\geq...\geq c_m\)。
证明：若 \(p_1<p_2,c_1<c_2\)，我们可以交换这两个数的次数。
-
-
实现：
首先确定枚举的最大质数以及质因子的最大次数。然后 dfs 即可。
以 P1463 为例，求出不超过 \(n\) 的最大的反素数。
void dfs(ll v,int cnt,int id,int lim) {
//v 当前的数，cnt 当前数的约数个数，id 枚举到的质数编号，lim 质因子次数上的限制
if(cnt>maxx||(cnt==maxx&&v<ans)) {ans=v,maxx=cnt;}
if(id>10) return ;
for(int i=1;i<=lim;i++) {
if((t=v*qpow(p[id],i))>n) break;
dfs(t,cnt*(i+1),id+1,i);
}
}
- 应用：
- 求约数一定的最小数
- 求 \(n\) 以内因子数最多的数
参考资料
- OI Wiki
- Cai の 课件
- 【OI笔记】数论
- Miller Rabin算法详解 - 自为风月马前卒 - 博客园
- BSGS算法及扩展 - Cyhlnj - 博客园
- 算法学习笔记(25): 卢卡斯定理 - 知乎
- 扩展Lucas定理 - HorizonWind 的博客 - 洛谷博客
- 莫比乌斯反演学习笔记 - _YangZJ - 博客园
- min_25筛 - 小蒟蒻yyb - 博客园
- Min25 筛学习笔记 - _YangZJ - 博客园
- 就在，刚刚开始熟悉这个城市的温度的时候，我愿为你流泪 - 致逝者的摇篮 - 洛谷博客
- 我们仍未理解那天所学习的数论算法 - ReClouds の 小屋 - 洛谷博客
致谢：
感谢 yb 给了当大冤种的机会。
感谢鉴God 教会了 Min_25。
感谢帝王教会了 Pollard rho，并且帮脑瘫 ty debug。
感谢 Cai 提供了一些不知名支持。
标签：frac,gcd,limits,ty,pmod,sum,Difficult,math,equiv From： https://www.cnblogs.com/ty-tyty/p/17166058.html