自己重新推一遍柿子。/fendou

P2568 GCD

题目传送门

求 $$ \sum\limits_{p\in prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=p] $$ gcd的套路转换( $$ \sum\limits_{p\in prime}\sum\limits_{i=1}^{\lfloor \frac{n}{p} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{p} \rfloor}[\gcd(i,j)=1] $$ 然后发现 $\sum[\gcd(i,j)=1]$ 这不欧拉函数吗，但是由于是有序数对，所以有 $$ \sum\limits_{p\in prime}2\times\sum\limits_{i=1}^{\lfloor \frac{n}{p} \rfloor}\varphi(i)-1 $$ 减一是因为$i=j$ 时会被重复算，最后复杂度 $\mathcal{O(n)}$。

P2398 GCD SUM

题目传送门

求 $$ \sum\limits_{i=1}^n \sum\limits_{j=1}^n \gcd(i, j) $$ 根据欧拉函数 $n=\sum\limits_{d\mid n}\varphi(d)$ 的性质，有 $$ \sum\limits_{i=1}^n \sum\limits_{j=1}^n\sum\limits_{d\mid \gcd(i,j)} \varphi(d) $$ 也就是为 $$ \sum\limits_{i=1}^n \sum\limits_{j=1}^n\sum\limits_{d\mid i,j} \varphi(d) $$ 考虑每个 $\varphi(d)$ 的贡献，于是原式 $$ \sum\limits_{i=1}^{n}\varphi(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{i}\rfloor $$ 最后 $\mathcal{O(n)}$ 求解即可，其实也可以整除分块，但没必要。 （好像这些转化叫欧拉函数反演？）

P2261 余数求和

题目传送门

求 $$ \sum\limits_{i = 1}^n k \bmod i $$ 有 $$ \sum\limits_{i=1}^n k-\lfloor\frac{k}{i}\rfloor\times i $$ 将 $k$ 提出来 $$ nk-\sum\limits_{i=1}^n\lfloor\frac{k}{i}\rfloor\times i $$ 这样就可以用整除分块 $\mathcal{O(\sqrt n)}$ 计算了。

P4139 上帝与集合的正确用法

题目传送门

求 $$ 2^{2^{2^{…}}}\bmod p $$ 有一个东西叫扩展欧拉定理，若 $\varphi(p)\leq b$，则 $$ a^b=a^{b \bmod \varphi(p)+\phi(p)} $$ 所以可以对指数递归求解。

P2522 [HAOI2011] Problem b

题目传送门

多组数据，求 $$ \sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}[\gcd(i,j)=k] $$ 可以转化成求 $1$ ~ $n$ 和 $1$~$m$ 的，最后容斥一下就行了 $$ f(k)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=k] $$ 有 $$ \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1] $$ 由莫比乌斯函数的性质 $\sum\limits_{d\mid n}\mu(d)=[n=1]$ 可有 $$ \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d\mid \gcd(i,j)}\mu(d) $$ 遇到整除式可以尝试改成枚举式，这里枚举一下 $d$，上界为 $\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)$，所以不妨设 $n\leq m$ ，于是原式 $$ \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{x=1}^{\lfloor\frac{n}{k} \rfloor}\mu(x)\times[x\mid \gcd(i,j)] $$ 发现要满足 $x\mid\gcd(i,j)$，$i$ 和 $j$ 必须要是 $x$ 的倍数，所以有 $$ \sum\limits_{x=1}^{\lfloor\frac{n}{k} \rfloor}\mu(x)\times \lfloor\frac{a}{xd}\rfloor\times \lfloor\frac{b}{xd}\rfloor $$ 然后整除分块，启动！

P2257 YY的GCD

题目传送门

多组数据，求 $$ \sum\limits_{p\in prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=p] $$ 转化为 $$ \sum\limits_{p\in prime}\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(i,j)=1] $$ 是不是可以仿照一下上题 $$ \sum\limits_{p\in prime}\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum\limits_{x|\gcd(i,j)}\mu(x) $$ $$ \sum\limits_{p\in prime}\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\mu(x)\times[x\mid\gcd(i,j)] $$ $$ \sum\limits_{p\in prime}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\mu(x)\times\lfloor\frac{n}{xp}\rfloor\times\lfloor\frac{m}{xp}\rfloor $$ 然后就不会了/hsh，去看了看题解，感觉很妙啊，设 $T=xp$，则有 $$ \sum\limits_{p\in prime}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\mu(x)\times\lfloor\frac{n}{T}\rfloor\times\lfloor\frac{m}{T}\rfloor $$ 然后枚举 $T$，有 $$ \sum\limits_{p\in prime}\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\times\lfloor\frac{m}{T}\rfloor\times\mu(\frac{T}{p}) $$ $p$ 只与 $\mu(\frac{T}{p})$ 有关，可以把他们单独放到一起 $$ \sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\times\lfloor\frac{m}{T}\rfloor\times\sum\limits_{p\in prime}\mu(\frac{T}{p}) $$

P1829 [国家集训队] Crash的数字表格 / JZPTAB

题目传送门

求 $$ \sum\limits_{i=1}^n\sum\limits_{j=1}^m \operatorname{lcm}(i,j) \bmod 20101009 $$ 易知 $$ \sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{i\times j}{\gcd(i,j)} $$