机房卷哥让我写的。
大部分是习题总结。
不如 Wiki
- 两个积性函数 \(f,g\) ，它们的 狄利克雷卷积(Dirichlet卷积) 为
记为 \(h=f*g\) .
- 狄利克雷卷积满足 交换律，结合律，且得到的函数也是 积性函数 。
定义
\[\epsilon(n)=\lbrack n=1 \rbrack,I(n)=1,id(n)=n \]\(\epsilon\) 即该运算意义下的单位元，因为一定有
\[g(n)=(f * \epsilon)(n)=\sum_{d|n}f(d)\epsilon(\frac{n}{d})=f(n) \]即 \(g=f,f=f*\epsilon\) .
常用函数的三个结论：
- \(\mu * I=\epsilon\)
即证
\[\sum_{d|n}\mu(d)=\lbrack n=1 \rbrack \]\(n=1\) 时显然成立。
设 \(n=\prod_{i=1}^{m}{p_i}^{c_i}\) ,当 \(d\) 有平方因子 ( 不包括 \(1\) ) 时贡献为 \(0\) .
令 \(n'=\prod_{i=1}^{m}p_i\) ，求 \(\sum_{d|n'}\mu(d)\) 即可。
容易发现 \(n\) 的所有质因子有 \(2^m\) 种组合，枚举质因子的个数，即
\[\sum_{i=0}^{m}(-1)^i C(m,i)=(-1+1)^m=0 \]得证。
- \(\varphi * I=id\)
即 \(\sum_{d|n}\varphi(d)=n\) ，这里不写。
- \(id * \mu=\varphi\)
用的不会很多。
利用狄利克雷卷积的结合律，在前一个式子的两边乘上一个 \(\mu\) ，由 \(\mu * I=\epsilon\) 可推该式。
求满足 \(1 \leq a \leq n\)，\(1 \leq b \leq m\)，且 \(\gcd(a,b)=d\) 的二元组 \((a,b)\) 的数量。
\(1 \leq T \leq 5 \times 10^4\)，\(1 \leq d \leq n,m \leq 5 \times 10^4\)。
本文默认 \(n\le m\) .
令 \(n\rightarrow\lfloor\frac{n}{d}\rfloor,m\rightarrow\lfloor\frac{m}{d}\rfloor\) ，求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\lbrack gcd(i,j)=1 \rbrack \]后面的艾弗森括号就等价于 \(\epsilon(gcd(i,j))\)，展开得到
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d) \]把 \(d\) 提到前面：
\[\sum_{d=1}^{n}\mu(d)\lfloor \frac{n}{d}\rfloor\lfloor \frac{m}{d}\rfloor \]预处理 \(\mu\) 并做前缀和，询问时 \(O(\sqrt{n})\) 整除分块即可。
条件变成 \(gcd\) 为质数。
\(1 \leq T \leq 10^4\)，\(1 \leq n,m \leq 10^7\)。
枚举 \(gcd(i,j)\) 可得
\[\sum_{d=1}^{n}\lbrack d\in Prime\rbrack\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}\lbrack gcd(i,j)=1\rbrack \]\[\sum_{d=1}^{n}\lbrack d\in Prime\rbrack\sum_{p=1}^{\lfloor \frac{n}{d}\rfloor}\mu(p)\lfloor \frac{n}{dp}\rfloor\lfloor \frac{m}{dp}\rfloor \]有一个trick，令 \(T=dp\) ，然后再把 \(T\) 提到前面去：
\[\sum_{T=1}^{n}\lfloor \frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})\lbrack d\in Prime\rbrack \]后半部分的东西可以 \(O(n\space log\space log\space n)\) 求出来，询问也是 \(O(\sqrt{n})\) 的。
还有trival的例题不写了。
-
若 \(g(n)=\sum_{d|n}f(d)\) ，则 \(f(n)=\sum_{d|n}g(d)\mu(\frac{n}{d})\) .
-
若 \(g(n)=\sum_{n|d}f(d)\) ，则 \(f(n)=\sum_{n|d}g(d)\mu(\frac{d}{n})\) .
这两个式子称为 莫比乌斯变换 。两个函数 不需要一定是积性函数 。
第一个：由 \(g=f * I\) 显然可以得到 \(f=g * \mu\) .
第二个：反推。
\[\sum_{n|d}g(d)\mu(\frac{n}{d}) \]\[\sum_{d=1}\mu(d)g(nd) \]\[\sum_{d=1}\mu(d)\sum_{nd|p}f(p) \]\[\sum_{p=1}f(np)\sum_{d|p}\mu(d) \]\[=f(n) \]一个长为 \(n\) ，值域为 \(L,R\) 的数列 \(A\) ，求
\[\sum_{A}\lbrack \gcd_{i=1}^{n}A_i=k\rbrack \]\(n,L,R,k\le10^9,R-L\le10^5\) .
先将 \(L\rightarrow\lceil\frac{L}{k}\rceil\) , \(R\rightarrow\lfloor\frac{R}{k}\rfloor\) .
记 \(f(m)\) 为 \(gcd\) 刚好为 \(m\) 的种数，\(g(m)\) 为 \(gcd\) 为 \(m\) 的倍数的种数，那么 \(f(1)\) 即为所求。
容易得到：
\[g(m)=\sum_{m|d}f(d) \]\[f(m)=\sum_{m|d}\mu(\frac{d}{m})g(d) \]想一下怎么得到每一个 \(g(m)\) .
显然就是
\[g(m)=(\lfloor\frac{R}{m}\rfloor-\lfloor\frac{L-1}{m}\rfloor)^n \]答案是
\[f(1)=\sum_{i=1}\mu(i)g(i) \]一样的 \(g\) 可以整除分块，所以要做 \(\mu\) 的前缀和。
要用杜教筛，还没写到，可以往下翻，本题是一道典型的莫比乌斯变换。
几道比较有意义的题。
肥肠有意思的题。
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_1(gcd(i,j))\lbrack \sigma_1(gcd(i,j))\le a\rbrack \]\(\sigma_1\) 是因子之和。
\(T\le 2\times 10^4,n,m\le 10^5 ,|a|\le 10^9\) .
不考虑 \(a\) ，那么
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_1(gcd(i,j)) \]\[\sum_{d=1}^{n}\sigma_1(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)\lfloor \frac{n}{dp}\rfloor\lfloor \frac{m}{dp}\rfloor \]\[\sum_{T=1}^{n}\lfloor \frac{n}{T}\rfloor\lfloor \frac{m}{T}\rfloor\sum_{d|T}\sigma_1(d)\mu(\frac{n}{d}) \]如果套上 \(a\) 直接做单次是 \(O(n\space log\space n)\) 的。
考虑离线，将所有的 \(\sigma_1(d)\) 和询问的 \(a\) 排序，更换询问时就能不重复地添加。
统计答案时要用到整除分块，所以应该得到一个区间和的形式，用树状数组实现操作。
这样复杂度就是 \(O(n\space log^2\space n+T\sqrt{n}\space log\space n)\) .
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) \]\(d\) 是约数个数，也可以写成 \(\sigma_0\) .
怎么算 \(d(ij)\) : \(i,j\) 的两个互质的约数相乘起来，产生的贡献是不重复的，也就是
\[\sum_{x|i}\sum_{y|j}\lbrack gcd(x,y)=1\rbrack \]\[\sum_{p|gcd(i,j)}\mu(p)d(\frac{i}{p})d(\frac{j}{p}) \]代回去：
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{p|gcd(i,j)}\mu(p)d(\frac{i}{p})d(\frac{j}{p}) \]\[\sum_{p=1}^{n}\mu(p)\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p}\rfloor}d(i)d(j) \]就做完了。
P1829 [国家集训队]Crash的数字表格 / JZPTAB
这个也是简单模板，有个 \(lcm\) 而已。
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) \]\(n,m\le 10^7\) .
\[\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{d}\lbrack gcd(i,j)=d\rbrack \]\[\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\lbrack gcd(i,j)=1\rbrack \]把后面那个东西提出来单独做式子看起来舒服方便一点。
后半可以整除分块。
代回去：
\[\sum_{d=1}^{n}d\cdot S(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor) \]也可以整除分块。
分块套分块的复杂度是 \(O(n^{\frac{3}{4}})\) 的。
求
\[\sum_{1\le a<b\le n}\lbrack a+b|\space ab\rbrack \]\(n<2^{31}\) .
当 \(gcd(a,b)=1\) 时，显然有 \(a+b\not|\space ab\) .
设 \(a=di,b=dj\) ，那么 \(i+j|\space ijd\) .
因为 \(i+j\not|\space ij\) ，所以 \(i+j|\space d\).
\[\sum_{i=1}^{n}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{i+j}\rfloor\lbrack gcd(i,j)=1\rfloor \]当 \(i>\sqrt{n}\) 时里面式子就恒为 \(0\) 了。
\[\sum_{i=1}^{\sqrt{n}}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{i+j}\rfloor\lbrack gcd(i,j)=1\rfloor \]\[\sum_{i=1}^{\sqrt{n}}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{i+j}\rfloor\sum_{p|i,p|j}\mu(p) \]\[\sum_{p=1}^{\sqrt{n}}\mu(p)\sum_{i=1}^{\lfloor\frac{\sqrt{n}}{p}\rfloor}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{ip}\rfloor}{ip+jp}\rfloor \]\[\sum_{p=1}^{\sqrt{n}}\mu(p)\sum_{i=1}^{\lfloor\frac{\sqrt{n}}{p}\rfloor}\sum_{j=1}^{i-1}\lfloor\frac{\lfloor\frac{n}{ip^2}\rfloor}{i+j}\rfloor \]暴力枚举 \(p,i\) ，后面的式子是可以整除分块的。
大家想看的东西。
求
\[\sum_{i=1}^{n}\varphi(i) \]\[\sum_{i=1}^{n}\mu(i) \]\(T\le 10\) ，$ n<2^{31} $ .
设待求函数为 \(f\) ，其前缀和为 \(S\) ，且 \(h=f * g\) ，那么 \(h\) 的前缀和
\[\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d}) \]\[\sum_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) \]显然有
\[g(1)S(n)=\sum_{i=1}^{n}h(i)-\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor) \]任务是找到方便计算前缀和的 \(g,h\) ，简化原式的计算。
\(f=\varphi\) ，取 \(g=I,h=id\) ，\(h\) 的前缀和就是 \(\frac{n(n+1)}{2}\) ，\(g\) 的前缀和就是 \(n\) .
\(f=\mu\) ，取 \(g=I,h=\epsilon\) ， \(h\) 的前缀和就是 \(1\) 。
大概预处理 \(10^6\) 级别的答案，询问时暴力整除分块，得到的答案可以用 \(map\) 或者 \(unordered\space map\) 存下来.
代码不放，自己去贺。
复杂度是 \(O(n^{\frac{2}{3}})\) 的。
大招
求
\(\sum_{x=1}^{n}\sum_{y=1}^{m}\) ，\(\frac{x}{y}\) 为最简分数，且在 \(k\) 进制下是纯循环小数或整数。
\(n,m\le10^9,2 \le k \le 2\times10^3\)
设循环节长度为 \(l\) ，则 \(\frac{x}{y}\) 和 \(\frac{xk^l}{y}\) 的小数部分相等。
\[\frac{x}{y}-\lfloor\frac{x}{y}\rfloor=\frac{xk^l}{y}-\lfloor\frac{xk^l}{y}\rfloor \]\[x-\lfloor\frac{x}{y}\rfloor* y=xk^l-\lfloor\frac{xk^l}{y}\rfloor* y \]\[x\equiv xk^l\space (mod\space y) \]由 \(\frac{x}{y}\) 为最简分数得 \(gcd(x,y)=1\) :
\[k^l\equiv 1\space (mod\space y) \]答案就是
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\lbrack gcd(i,j)=1\rbrack\lbrack gcd(j,k)=1\rbrack \]其中的一种方法：
\[\sum_{j=1}^{m}\lbrack gcd(j,k)=1\rbrack\sum_{i=1}^{n}\sum_{d|gcd(i,j)}\mu(d) \]\[\sum_{j=1}^{m}\lbrack gcd(j,k)=1\rbrack\sum_{d|j}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor \]\[\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lbrack gcd(dj,k)=1\rbrack \]\[\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor\lbrack gcd(d,k)=1\rbrack\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lbrack gcd(j,k)=1\rbrack \]把后面那串式子记成
\[f(n)=\sum_{i=1}^{n}\lbrack gcd(i,k)=1\rbrack \]显然有
\[f(n)=\lfloor\frac{n}{k}\rfloor\varphi(k)+f(n\space mod\space k) \]\(k\) 以内的部分可以直接算。
考虑计算
\[g(n,k) =\sum_{d=1}^{n}\mu(d)\lbrack gcd(d,k)=1\rbrack \]\[\sum_{d=1}^{n}\mu(d)\sum_{p|d,p|k}\mu(p) \]\[\sum_{p|k}\mu(p)\sum_{p|d}\mu(d) \]\[\sum_{p|k}\mu(p)\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(dp) \]无效贡献对式子无影响，变成
\[\sum_{p|k}\mu(p)\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(dp)\lbrack gcd(d,p)=1\rbrack \]\[\sum_{p|k}\mu(p)\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\mu(p)\lbrack gcd(d,p)=1\rbrack \]\[\sum_{p|k}\mu^2(p)\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lbrack gcd(d,p)=1\rbrack \]\[\sum_{p|k}\mu^2(p)g(\lfloor\frac{n}{p}\rfloor,p) \]边界值 \(g(0,k)=0\) ，\(g(n,1)=\sum_{d=1}^{n}\mu(d)\) .
然后就要用杜教筛。
求
\[\sum_{i=1}^{n}\sum_{j=1}^{n}ij\cdot gcd(i,j) \]答案对质数 \(p\) 取模 。
一个较妙的做法。
\[\sum_{i=1}^{n}\sum_{j=1}^{n}ij\cdot id(gcd(i,j)) \]这里用到 \(\varphi * I =id\) .
\[\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|i,d|j}\varphi(d) \]\[\sum_{d=1}^{n}\varphi(d)\sum_{d|i}\sum_{d|j}ij \]\[\sum_{d=1}^{n}\varphi(d)\cdot d^2\cdot(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i)^2 \]\(\lfloor\frac{n}{d}\rfloor\) 可以整除分块，里面的式子的前面和需要杜教筛。
也就是 \(f=\varphi\cdot id^2\) ，考虑取 \(g=id^2\) ，那么
\(h(n)=\sum_{d|n}f(d)g(\frac{n}{d})=n^2\cdot\sum_{d|n}\varphi(n)=n^3\) .
即 \(h=id^3\) .
然后杜教筛就不难了。
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(ij) \]\(T\le10^4,n,m\le10^5\) .
有个结论：
\[\varphi(ij)=\frac{\varphi(i)\varphi(j)d}{\varphi(d)} \]\(d=(i,j)\) ，这个结论还是很好证的。
\[\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(id)\varphi(jd)\lbrack gcd(i,j)=1\rbrack \]\[\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{dp}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dp}\rfloor}\varphi(idp)\varphi(jdp) \]\[\sum_{T=1}^{n}\sum_{d|T}\frac{d\mu(\frac{T}{d})}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jT) \]前面那坨函数记为 \(f(T)\) .
记 \(G(y,x)=\sum_{i=1}^{x}\varphi(iy)\) ，也就是
\[\sum_{T=1}^{n}f(T)\cdot G(\lfloor\frac{n}{T}\rfloor,T)\cdot G(\lfloor\frac{m}{T}\rfloor,T) \]显然这个式子只能 \(O(n)\) ，直接T飞。
所以再记一个 \(S(y,z,x)=\sum_{T=1}^{x}f(T)\sum_{i=1}^{y}\varphi(iT)\sum_{j=1}^{z}\varphi(jT)\)
考虑递推，容易得到
\[G(y,x)=G(y,x-1)+\varphi(xy) \]\[S(y,z,x)=S(y,z,x-1)+f(x)\cdot G(x,y)\cdot G(x,z) \]接着就可以用牛逼分治，就是说设一个阈值 \(B\) ，对于 \(\lfloor\frac{n}{T}\rfloor\le B\) 的部分直接算，后面的再用分块算，有点不好看懂放个代码。
int query(int n,int m){
if(n>m)swap(n,m);
int ret=0;
for(int i=1;i<=m/B;i++)
(ret+=1ll*f[i]*G[i][n/i]%Mod*G[i][m/i]%Mod)%=Mod;
for(int x=m/B+1,gx;x<=n;x=gx+1){
gx=min(n/(n/x),m/(m/x));
(ret+=(S[n/x][m/x][gx]-S[n/x][m/x][x-1]+Mod)%Mod)%=Mod;
}
return ret;
}
算下复杂度是 \(O(n\space ln\space n+nB^2+T(\sqrt{n}+\frac{n}{B}))\) .
平衡复杂度不太会算，应该是取 \(B=T^{\frac{1}{3}}\) ，平衡复杂度 \(O(n\space ln\space n+T\sqrt{n}+nT^{\frac{2}{3}})\) .
所以就是牛逼东西。
这道题也是一样的trick.
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi\Big(\frac{lcm(i,j)}{gcd(i,j)}\Big) \]\[\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(ij)\lbrack gcd(i,j)=1\rbrack \]\[\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\varphi(i)\varphi(j)\lbrack gcd(i,j)=1\rbrack \]\[\sum_{d=1}^{n}\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum_{i=1}^{\lfloor\frac{n}{dp}\rfloor}\varphi(ip)\sum_{j=1}^{\lfloor\frac{m}{dp}\rfloor}\varphi(jp) \]\[\sum_{T=1}^{n}\sum_{d|T}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(id)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jd) \]一样记 \(G(y,x)=\sum_{i=1}^{x}\varphi(iy)\) ，
\(S(y,z,x)=\sum_{T=1}^{x}\sum_{d|T}\mu(d)\cdot G(d,y)\cdot G(d,z)\)
那么
\[G(y,x)=G(y,x-1)+\varphi(xy) \]\[S(y,z,x)=S(y,z,x-1)+\sum_{d|x}\mu(d)\cdot G(y,d)\cdot G(z,d) \]阈值为 \(B\) ，算下时间应该是 \(O(B^2\space n\ln n+T(\sqrt{n}+\frac{n}{B}\ln\frac{n}{B}))\) .
平衡复杂度不会算就乱取一个。
\(n\times n\) 的表格满足：
\[f(a,b)=f(b,a) \]\[b\times f(a,a+b)=(a+b)\times f(a,b) \]一开始有 \(f(a,b)=a\times b\)，满足表格的条件。
\(m\) 次操作，每次一个格子的数被修改且波及其他格子。然后给出 \(k\)，求左上角 \(k\times k\) 的矩阵的数之和。答案对 \(\rm 1e9+7\) 取模。
\(m\le10^4\)，\(n\le 4\times10^6\)，值域 \(\rm 1e18\).
从表格的对称性入手：
\[\gcd(a,a+b)=\gcd(a+b,a)=\gcd(a,a+b-a)=\gcd(a,b) \]所以修改 \((a,b)\) 的值会影响到 \(\gcd(x,y)=\gcd(a,b)\) 的 \((x,y)\) 的值。
转换一下第二个式子：
\[\frac{f(a,b)}{a\times b}=\frac{f(a,a+b)}{a\times(a+b)} \]辗转相除的过程中一直递归下去：
\[\frac{f(a,b)}{a\times b}=\frac{f((a,b),(a,b))}{(a,b)^2} \]那么
\[d\leftarrow (a,b),f(a,b)=\frac{ab}{d^2}\cdot f(d,d) \]记 \(f(d,d)\) 为 \(f(d)\)，即求
\[\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{ij}{d^2}\cdot f(d,d) \]枚举 \(\gcd\)：
\[\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[i\perp j]ij \]后面的式子由于有
\[\sum_{i=1}^{n}[i\perp n]i=\frac{n\varphi(n)+\epsilon(n)}{2} \]思考一下就变成了
\[\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i^2\varphi(i) \]记 \(\displaystyle S(n)=\sum_{i=1}^{n}i^2\varphi(i)\)，就可以整除分块了。
然后发现 \(f\) 是动态的而且还要作前缀和。
不考虑数据结构的复杂度是 \(O(m\sqrt{n})\) 的。
\(O(1)\) 查询不难想到分块，把 \(f\) 变为前缀和序列，单点修改改为区间修改，这样总复杂度 \(O(m\sqrt{n})\).
分块被卡成了儿子。。。树状数组跑得十分快。
标签：lfloor,frac,gcd,乌斯,sum,rfloor,mu,反演,莫比 From： https://www.cnblogs.com/SError0819/p/17609849.html