- 数论下
- 前言
- 因数与数论函数
- 基础
- 基础概念与定义
- 整数唯一分解定理/算术基本定理
- 素数判定/分解质因数/得到约数
- 数论分块(整除分块)
- 数论函数相关
- 积性函数
- 筛法
- 埃氏筛
- 欧拉筛
- 杜教筛
- Powerful Number筛
- Min_25筛
- 洲阁筛
- 莫比乌斯反演
- 前置:Dirchlet 卷积
- 标准莫反
- 莫反例题
- 基础
数论下
前言
叠甲:本文的许多定义并不是最官方严谨的,但是其实是本质相同的,不过更偏实用一点。有部分内容我并没有写代码验证过,可能有错,希望发现问题的大佬能及时指出。欢迎转载。但如果是全文转载,请附上原文链接。因为博客园与本地的渲染有细微差别,可能会导致有少量格式错误,但应该不会影响阅读,也欢迎大佬指出。
这不是给数论初学者写的博客!这是作者在整理各种数论知识的边边角角梳理出来的文章,不保证内容按照难度递增,而是按照逻辑顺序排列的,相关联的知识点会放在一起。文章分为前、中、后和配套题目与题解四个部分,分成四偏文章的原因是,放在一起会导致非常卡,猜测是因为文章太大了,每个部分之间有着藕断丝连的关系,前三部分是知识点,有着互相依赖的逻辑关系(但是保证不会有自己证明自己的情况出现),第四篇是具体的题目,对提分来说更加重要。建议配合食用。
本文很多内容是我之前写的博客复制过来,修缮了一下,个人感觉比之前写的更本质,更清晰一点,还有不少内容是我这次整理新学的知识。四篇文章总源码超过 100 KB,我认为整理的还是比较全面了,没有涉及到的内容,大概率在数论练习题里的后记里面提及。
合集链接:数论上,数论中,数论下,数论练习题。
因数与数论函数
基础
基础概念与定义
- 素数
- 因数
- 倍数
- 约数
- 最小公因数/最大公倍数
不用做过多解释。
整数唯一分解定理/算术基本定理
内容:任何一个大于 \(1\) 的正整数都可以被唯一分解成有限个质数的次幂的乘积。
证明:感性理解即可。不会真的有人会想要去严谨证明这个东西吧?
素数判定/分解质因数/得到约数
- 试除法
本质上是根号分治。只枚举 \([1,\sqrt n]\),判断它是不是 \(n\) 的约束,一般用这个足够了。不过多解释。
- 倍数法
用于要处理 \([1,N]\) 之间所有数的约数之类的问题。
可以理解为筛法。对于每一个数,标记它的所有倍数含有它这个因子。复杂度就是标准的调和级数 \(O(N\log N)\)。当然也可以只标注每个数的最小质因子,通过每次除掉它的最小质因子,可以分解出它的所有质因数,这个随便用个什么筛法都能筛出来。
这也恰好说明了约数个数平均下来是 \(O(\log N)\) 的。
找到一个倍数法的水题:P7960 NOIP2021报数 - 洛谷,这个题就是倍数法标记不合法的数,加点剪枝。
- Miller_Rabin ~ Pollard Rho(理性愉悦,不用讲)
前者 \(O(\log n)\),有一个比较大的常数;后者 \(O(n^{1\over4})\) ,但是是期望复杂度,实则跑的飞快。
如果要求约数,可以在分解了质因数后 dfs 其指数。
把之前写的博客粘过来后觉得格式太丑了,于是没粘过来,所以要学的同学直接去看我之前写的博客即可,我认为写得非常详细。详见这里.
数论分块(整除分块)
对于类似于 \(solve_{d=1}^{n}(\frac{n}{d})\) 的式子, \(\frac{n}{d}\) 的值的个数不超过 \(\sqrt n\) 个(下面有证明),故可以对于每一个结果去计算其贡献。
代码如下:
for(int l = 1, r; l <= n; l = r + 1) {r = n / (n / l);// d 在区间 [l, r] 的 n/d 大小相同ans += n / l * solve(l, r);
}
复杂度证明:
记 \(\dfrac{n}{d}\) 为 \(x\)。\(x\) 的取值范围在 \([1,n]\)。容易发现,\([1,\sqrt n]\) 的 \(x\) 更密集,\((\sqrt n, n]\) 的 \(x\) 更稀疏。
因为 \(d\) 从 \(1\) 到 \(n\) ,只有 \(d\) 在 \([1, \sqrt n]\) 时,\(\dfrac{n}{d}\) 在 \((\sqrt n, n]\),所以\(\dfrac{n}{d}\) 在 \((\sqrt n, n]\) 的个数不超过 \(\sqrt n\).
\(\dfrac{n}{d}\) 从 \(1\) 到 \(\sqrt n\) 一共 \(\sqrt n\) 个数,所以总个数为 \(O(\sqrt n)\) 的,本质上就是一个根号分治的思想。
一般式子中出现下取整,并且是分母一直在变,直接无脑整除分块。(P.S. 如果是分子在变,可以考虑类欧或万欧,分子分母都在变,可以考虑是否可让一个不变)
\(solve_{d=1}^{n}(\frac{a}{d}\frac bd)\) 这种式子也可以整除分块。
for(int l = 1, r; l <= n; l = r + 1) {r = min({n, a / (a / l), b / (b / l)});ans = ans + 1ll * (b / l) * (a / l) * (sm[r] - sm[l - 1]);
}
复杂度 \(O(\sqrt n)\)。
这相当于在数轴上对 \(a\) 撒 \(O(\sqrt n)\) 个点,对 \(b\) 撒 \(O(\sqrt n)\) 个点,加起来还是 \(O(\sqrt n)\) 个点。
数论函数相关
积性函数
- 基础定义
积性定义: \(f(ab)=f(a)f(b)\) ( \(a,b\) 互质时)
具有积性的函数叫积性函数。
如果 \(a,b\) 不互质时上式仍然成立,那就是完全积性函数。
边界:积性函数在 \(1\) 处的取值为 \(1\)。这样定义更为方便,不然每次都要分讨 1 的情况很麻烦。
- 积性函数性质(摘自 oi-wiki,并给出了 oi-wiki 不屑于写的证明)
对正整数 \(x\) ,设其唯一质因数分解为 \(x=\prod p_{i}^{k_{i}}\) ,其中 \(p_{i}\) 为质数。
若 \(F(x)\) 为积性函数,则有 $F(x)=\prod F\left(p_{i}^{k_{i}}\right) $ 。
若 \(F(x)\) 为完全积性函数,则有 $F(x)=\prod F\left(p_{i}^{k_{i}}\right)=\prod F\left(p_{i}\right)^{k_{i}} $ 。
若 \(f(x)\) 和 \(g(x)\) 均为积性函数,则以下函数也为积性函数:
- \(h(x)=f\left(x^{p}\right)\)
证明:
设 \(a\) 和 \(b\) 是互质的整数,我们需要证明 \(h(ab) = h(a)h(b)\)。
由于 \(f\) 是积性函数,我们有:
因此,\(h(x) = f(x^p)\) 是积性函数。
- \(h(x) =f(x) g(x)\)
证明: \(h(ab) = f(ab)g(ab) = (f(a)f(b))(g(a)g(b)) = (f(a)g(a))(f(b)g(b)) = h(a)h(b)\).
推论:\(h(x) =f^{p}(x)\).
- \(h(x) =\sum_{d \mid x} f(d) g\left(\frac{x}{d}\right)\)
证明:
由于 \(a\) 和 \(b\) 互质,\(d\) 可以唯一地表示为 \(d = d_1d_2\),其中 \(d_1|a\) 且 \(d_2|b\)。因此,
由于 \(f\) 和 \(g\) 是积性函数,我们可以将上式重写为:
因此,\(h(x) = \sum_{d|x} f(d)g\left(\frac{x}{d}\right)\) 是积性函数。
最后这个性质是莫反的基础。
- 常见的积性函数
- 单位函数:\(\varepsilon(n)=[n=1]\)(完全积性)
- 恒等函数:\(\operatorname{id}_k(n)=n^k\)(完全积性),当 \(k=1\) 时,简记为 \(id(n)=n\)
- 常数函数:\(\operatorname{1}(n)=1\)(完全积性)
- 除数函数:\(\sigma_k(n)=\sum_{d|n}d^k\),特殊地,\(\sigma_0(n)\) 即因数个数,简记为 \(\operatorname{d}(n)\);\(\sigma_1(n)\) 即因数之和,简记为 \(\sigma(n)\)
- 欧拉函数:\(\varphi(n)=\sum_{d=1}^n[\gcd(d,n)=1]\)
- 莫比乌斯函数:\(\mu(x)=\begin{cases}1\ \ &(x=1)\\(-1)^k\ \ &(\text{x没有平方数因子,且x的质因子个数为k})\\0 &(\text{x有平方数因子})\end{cases}\)
这些积性函数都可以用线性欧拉筛 \(O(n)\) 地筛出。
除了积性函数,当然也可以定义加性函数,比如“质因子数目”就是一个加性函数,不过我目前没有发现加性函数有什么用。
筛法
- 概述
一般的筛法可以筛出某个范围内的素数。
用恰当的筛法可以筛出具有某种性质的数论函数,或某种数论函数的前缀和。
首先有一个朴素算法是枚举每个数,然后遍历它们的倍数,然后再计算这些数对它们的倍数的贡献。复杂度是 \(O(n\ln n)\).
埃氏筛
本质上是对朴素算法的优化,结果一不小心把复杂度优化了。
- 复杂度
\(O(n\log\log n)\) 并且常数很小,所以可以近似看作 \(O(n)\)。复杂度不会证明。OI-wiki
上给出了一些神秘常数优化方法,不过我没看懂。
- 适用范围
只需要筛素数的题。其实也可以筛一些简单的积性函数,不过不如欧拉筛。下文只讲筛素数的方法。
优化 1 :只用处理素数的倍数。这样每个合数都会被它某些素因子筛掉。
优化 2 :对于每一个素数 \(p\),只标记 \(p^2 + kp,k\ge0\) 为合数,也就是说直接从平方这里开始往后筛合数。
优化 2 的正确性:假设 \((p,p^2)\) 内存在一个含有 \(p\) 这个因子的合数没被筛掉,那这个合数一定可以被写为 \(pxq,x\in z,q\) 是这个合数的质因子,并且不同于 \(p\)。
因为 \(pxq\) 小于 \(p^2\),所以 \(q \le p\),所以这个数会被 \(q\) 筛掉,假设不成立。
所以可以每次遇到一个不是合数的数,就认为它是素数。
附上代码:
void ash_shai(int n) {ll i = 2; for(; i * i <= n; ++i) if(!vis[i]) {pri.push_back(i);for(ll j = i * i; j <= n; j += i) vis[j] = true;} for(; i <= n; ++i) if(!vis[i]) pri.push_back(i);
}
欧拉筛
又称线性筛。
-
原理:让每个数只被它的最小质因子筛掉
-
复杂度: \(O(n)\)
-
主要用处:筛积性函数值
我们对于每一个数 \(i\),枚举小于等于它的最小质因子并与其互质的质数 \(p\),把由它俩乘积肯定是合数,把这个合数筛掉。
正确性:考虑反证法。假设有一个数不是被它的最小质因子筛掉的,假设是 \(q\),因为 \(q\) 是质数,所以此时这个合数的最小质因子一定在 \(i\) 中,这不符合算法流程。假设有一个数没有被筛掉,假设它是 \(x\),它的最小质因子是 \(p\),那么在枚举 \(x/p\) 的时候一定会枚举到 \(p\),假设不成立。证毕。
每次遇到一个不是合数的数,就认为它是素数。
不过更重要的是用欧拉筛去筛函数值。
可以被欧拉筛筛出来的函数必须满足以下性质:
对于 \(k = 1, k \in prime, k \mid p\), \(f(pk)\) 可以由 \(f(p)\) 和 \(f(k)\) 快速得到,并且知道 \(f(1)\) 的值。
所以大部分的积性函数都可以用欧拉筛线性地筛出函数值。
例如 \(\varphi\) 和 \(\mu\):
\(\varphi(1) = \mu(1) = 1\)
\(\varphi(p) = p - 1, \mu(p) = 1\)
\(\varphi(pk) = \varphi(p)*\varphi(k) = (k-1)\varphi(p),\mu(pk) = \mu(p)*\mu(k) = -\mu(p)\),\(k\) 是质数,且 \(k,p\) 互质。
\(\varphi(pk) = k\varphi(p),\mu(pk) = 0,k \in prime, k\mid p\)
代码:
void get_oula(int M){phi[1] = 1, mu[1] = 1;for(int i = 2; i <= M; ++i) {if(!vis[i]) pri.push_back(i), phi[i] = i - 1, mu[i] = -1; // k=1for(int j : pri) {//k is primeif(i*j>M) break;vis[i*j] = 1;phi[i*j] = phi[i] * (j - 1);mu[i*j] = mu[i] * (-1);if(i % j == 0){//k | pphi[i*j] = phi[i] * j;mu[i*j] = 0;break;}}}
}

杜教筛
- 优缺点
优点:1. 复杂度 \(O(n^{2\over 3})\).2. 可以得到前缀和。
缺点:只能得到函数的部分函数值的前缀和。对要筛的函数有很多限制。
- 算法实现
对于数论函数 \(f\),计算 \(S(n)=\sum_{i=1}^{n}f(i)\)。
需要找到一个合适的函数 \(g\),来和 \(f\) 进行卷积。
如果 \(g(1),\sum_i^n(f\otimes g)(i),\sum^{n}_{d=2}g(d)\) 这三个都是能快速求到的,那么就可以用整除分块来递归地做。
最后一个问题:这个是什么时间复杂度?
观察到:当\(a,b\gt0\) 且 \(b\in \Z\) 时, \(\left\lfloor\frac{\lfloor\frac na\rfloor}{b}\right\rfloor=\left\lfloor\frac{n}{ab}\right\rfloor\),所以无论怎么递归,S 会计算到的数只在集合 \(\{\left\lfloor\frac nx\right\rfloor\}\) 中,只有 \(O(\sqrt n)\) 个。用微积分的知识,可以得到时间复杂度是 \(O(n^{3\over4})\)
不过我们还可以通过暴力预处理(欧拉筛)前面的 \(2\over3\),使时间复杂度降到 \(O(n^{2\over3})\).
最大的问题在与要有合适的 \(g\)。我们发现 常数函数 \(1\) 对 \(\varphi\) 和 \(\mu\) 就满足此性质。
把 \(\mu\) 带到我们的式子里:
即:
\(\operatorname{1}(i)\) 的前缀和就是 \(i\)。杜教筛时间复杂度 \(O(n^{\frac{2}{3}})\)
对于 \(\varphi\) 带到我们的式子里:
即:
\(\operatorname{1}(i)\) 的前缀和就是 \(i\)。杜教筛时间复杂度 \(O(n^{\frac{2}{3}})\)
我们还发现 \(\mu·id_k\) 和 \(\varphi·id_k\) 可以找到 \(id_k\) 作为它们的函数 \(g\)。(注:这里的点乘表示的是对应位置相乘,即 :\((f·g)(n) = f(n)g(n)\))

Powerful Number筛
这玩意相比杜教筛,优点是对 \(g\) 的限制更少,可以处理更积性的 \(f\),缺点是写起来更史。
- 前置:Powerful Number
定义:对于正整数 \(n\),记 \(n\) 的质因数分解为 \(n = \prod_{i=1}^{m} p_{i}^{e_{i}}\)。\(n\) 是 Powerful Number(简称 PN) 当且仅当 \(\forall 1 \le i \le m, e_{i} > 1\)。
PN 有如下性质:
-
所有 PN 都可以表示成 \(a^{2}b^{3}\) 的形式。
证明:若 \(e_i\) 是偶数,则将
\(p_{i}^{e_{i}}\) 合并进 \(a^{2}\) 里;若 \(e_i\) 为奇数,则先将 \(p_{i}^{3}\) 合并进 \(b^{3}\) 里,再将 \(p_{i}^{e_{i}-3}\) 合并进 \(a^{2}\) 里。 -
\(n\) 以内的 PN 有 \(O(\sqrt{n})\) 个。
证明:考虑枚举 \(a\),再考虑满足条件的 \(b\) 的个数,有 PN 的个数约等于
那么如何求出 \(n\) 以内所有的 PN 呢?线性筛找出 \(\sqrt{n}\) 内的所有素数,再 DFS 搜索各素数的指数即可。由于 \(n\) 以内的 PN 至多有 \(O(\sqrt{n})\) 个,所以至多搜索 \(O(\sqrt{n})\) 次。
Powerful Number筛要求存在一个函数 \(g\) 满足:
-
\(g\) 是积性函数。
-
\(g\) 易求前缀和。
-
对于质数 \(p\),\(g(p) = f(p)\)。
假设现在要求积性函数 \(f\) 的前缀和.
首先,构造出一个易求前缀和的积性函数 \(g\),且满足对于素数 \(p\),\(g(p) = f(p)\)。记 \(G(n) = \sum_{i=1}^{n} g(i)\)。
然后,设函数 \(h\) 满足 \(f = g \otimes h\),根据狄利克雷卷积的性质可以得知 \(h\) 也为积性函数,因此 \(h(1) = 1\)。
对于素数 \(p\),\(f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p) \implies h(p) = 0\)。根据 \(h(p)=0\) 和 \(h\) 是积性函数可以推出对于非 PN 的数 \(n\) 有 \(h(n) = 0\),即 \(h\) 仅在 PN 处取有效值。这是保证 PN 筛时间复杂度的基本原理。
现在,根据 \(f = g \ast h\) 有:
\(O(\sqrt{n})\) 找出所有 PN,计算出所有 \(h\) 的有效值。对于 \(h\) 有效值的计算,只需要计算出所有 \(h(p^c)\) 处的值,就可以根据 \(h\) 为积性函数推出 \(h\) 的所有有效值。
现在对于每一个有效值 \(d\),计算
\(h(d)G\left(\left\lfloor \dfrac{n}{d} \right\rfloor\right)\) 并累加即可得到 \(F(n)\)。
下面考虑计算 \(h(p^c)\),一共有两种方法:
- 直接推出 \(h(p^c)\) 仅与 \(p,c\) 有关的计算公式,再根据公式计算 \(h(p^c)\)
- 根据 \(f = g \ast h\) 有 \(f(p^c) = \sum_{i=0}^c g(p^i)h(p^{c-i})\),移项可得 \(h(p^c) = f(p^c) - \sum_{i=1}^{c}g(p^i)h(p^{c-i})\),现在就可以枚举素数 \(p\) 再枚举指数 \(c\) 求解出所有 \(h(p^c)\)。
复杂度 \(O(\sqrt n\log n)\),而且这个上界比较宽松。
可惜的是,我们没有 PN 筛的模板题。不过 Min_25 筛的模板题可以用 PN 筛来做。
Min_25筛
咕咕咕
洲阁筛
咕咕咕
莫比乌斯反演
前置:Dirchlet 卷积
定义 \(\otimes\) :
- Dirchlet 卷积的性质
首先根据积性函数的第三条性质,说明积性函数的 Dirchlet 卷积还是积性函数。
更深入的学习:狄利克雷生成函数浅谈 - 洛谷专栏,贝尔级数 - 博客园。
其中,使用 DGF
来理解各种高级筛法有奇效。
标准莫反
刚才积性函数性质那里得到这么一个东西,
如果把 \(g\) 函数当成常数函数 \(1\) ,则可得到:
若 \(f(x)\) 为积性函数,则 \(h(x)=\sum_{d\mid n} f(x)\) 也为积性函数。
如果现在已知的是 \(h(x)\) ,可否求出 \(f(x)\) 来?
这是一个反演的形式,也就是说,我们只需要构造一个合适的容斥系数即可解决上面的问题,这个系数就是大名鼎鼎的莫比乌斯函数。
我们希望定义一个函数 \(\mu\) 满足下面这个式子:
需要打表/分讨可以发现,当定义 \(\mu(x)=\begin{cases}1\ \ &(x=1)\\(-1)^k\ \ &(\text{x没有平方数因子,且x的质因子个数为k})\\0 &(\text{x有平方数因子})\end{cases}\) ,就可以满足这个式子。
先在有了莫反,考虑来证明这几个式子:
- \(\large{\mu\otimes 1 = \varepsilon }\)
因为 \(1(n) = \sum_{d\mid n}[d=1]\),写成反演的形式就是这个公式。
当然也可以定义 \(\mu\) 是满足这个式子的函数,然后再推导莫反,这是 \(\mu\) 的另一种理解方式。做题用的最多最多的就是这个式子。
- \(\large{\mu\otimes \operatorname{id} = \varphi }\)
推导:
- \(\large{\varphi\otimes 1 = id}\)
对上一个式子套一个莫反即可。
- \(1\otimes1 = \operatorname{d}\)
套定义即可,不必多说。
- \(id \otimes1 = \sigma\)
套定义即可,不必多说。
- \(id_k\otimes1 = \sigma_k\)
套定义即可,不必多说。
前两个换一种写法就是:\(\sum\limits_{d\mid n} \varphi (d) = n\), \(\sum\limits_{d\mid n} \mu (d) = [n=1]\)。这才是推式子经常遇到的。
后面三个式子本质相同,而且非常好理解。
个人感觉 \(\varepsilon\) 相当于积性函数中的单位元,\(\mu\) 相当于 \(1\) 的逆元
莫反例题
莫反的题目一般是直接套用上面这些二级结论,一般不用标准莫反式子本身,所以要重点讲一下莫反的题目。
不同莫反题的套路是很相似的。基本上看到有 \(\gcd,lcm,[k= 1]\) 之类的玩意就可以无脑套上莫反。
- **例题1 **
求:
令 \(S(n) = \sum^n_i i = (n + 1) * n / 2,T=kd\),那么上式等于:
后面是积性函数,用线性筛 \(O(n)\),前面整除分块。
积性证明:
设 \(f(pq) = \sum_{xy|pq}\mu(xy)xy\) (\(p,q\) 互质)
\(f(p)=\sum_{x|p}\mu(x)x,f(q)=\sum_{y|q}\mu(y)y\)
因为 \(p,q\) 互质,所以 \(x,y\) 整除 \(p,q\) 中的其中一个。
钦定 \(x \mid p, y \mid q\)(注意,如果 \(xy\mid p\) 则,等价于把 \(xy\) 看成新的 \(x\), 把 \(1\) 看作 \(y\), 这种情况会在之前统计过)
\(f(pq) = \sum_{xy|pq}\mu(xy)xy = \sum_{x|p}\mu(x)x\sum_{y|p}\mu(y)y=f(p)f(q)\)
对于 \(f(j^2p) = f(jp) + \sum\mu(j^2x)j^2x = f(jp)\),其中 \(j,p\) 互质。
\(f(p) = \mu(1)1 + \mu(p)p\),其中 \(p\) 是质数。
\(f(1)=\mu(1)1 = 1\)。
- 例2:P5518 MtOI2019 幽灵乐团 / 莫比乌斯反演基础练习题.
吐槽一下:这题是一道一点都不基础莫比乌斯反演基础练习题,要用到很多 \(\prod\) 的性质,不过也可以无脑 exp ln 转和式乱搞。
一些约定: \([i\perp j]\) 表示 \(\gcd(i,j)=1\),\([p]\) 表示 该项只在 p 为真时存在,在 p 为假的时候不存在。上界默认为 \(A,B,C\) 最大值。
下文大量运用:累乘性质.
一看就很恶心。
先转化题目:
括号里面等于 \({ij\over gcd(i,j)gcd(i,k)}\),可以先算分子贡献,再算分母贡献。
因为有:
所以我们可以只计算一下这两个式子的值:
现在这个题被转化成了六个子问题了,
Type = 0
1:\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}i\).
2:\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}gcd(i,j)\).
令 \(T=d\times g\),则:
中间括号里面用欧拉筛积性函数预处理,直接整除分块 \(O(\sqrt n)\).
Type = 1
1: \(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}i^{i*j*k}\).
记 \(\sum_1^n 1= S(n) = {n(n + 1)\over 2}\)
2:\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}gcd(i,j)^{ijk}\).
类似于 type=0 - 2 ,中间可以欧拉筛预处理,然后整除分块。
Type = 2
1 : \(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}i^{\gcd(i,j,k)}\).
整除分块以后,那三个下取整都是定值,现在要求的是 \(\prod_T x^{\varphi(T)} = x^{\sum_T\varphi(T)}\) 和 \(\prod_T T^{\varphi(T)}\).
左边的,可以通过求 \(\varphi\) 的前缀和,右边的,把 \(\varphi\) 筛出来以后可以算 \(T^{\varphi(T)}\),求一个前缀积即可。\(O(\sqrt n \log n + n)\).
2.\(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C}\gcd(i,j)^{\gcd(i,j,k)}\).
先看左边:
还是一个整除分块 + 欧拉筛。
再来看右边:
中间的还是可以欧拉筛,外层乍一看有两个 \(\prod\),但实际上是整出分块套整除分块,所以加起来是 \(O(\sqrt[3\over4] n\log n)\).