几道有意思的积性函数题
前言
最近在搞积性函数筛法之类的东西，选了几道有意思的题放在这里。
有公式恐惧症的勿看！
哗啦啦。
[UOJ188] [UR #13]Sanrd
一句话题意：求(sum_{i=1}^n p_{smax}(i))，(nleq 10^{11})
其中(p_{smax(i)})表示某个数的次大质因子，定义质数和(1)的(p_{smax}=0)。
min_25筛的简单应用。
先在第一步的时候把质数个数(g(n,|P|))给筛出来，然后进第二步。
第二步时，若当前在状态(S(n,j))，强制当前层选的质因子为最大质因子，然后用(p_{j-1})贡献答案。
注意特判最大质因子和次大质因子相同的情况。
结合上述思路，容易写出转移方程：
(S(n,j) = p_{j-1}( g(n,|P|)-(j-1) ) + sum_{k=j}^{|P|} sum_{e=1}^{p_{k}^{e+1}leq n} (S(lfloor frac{n}{p_k^e}
floor ,k+1) + p_k))。
[BZOJ3309] DZY Loves Math
一句话题意：线性筛出 (G(T) = sum_{d|T}mu(frac{T}{d}) f(d)) ，(Tleq 10^7)。
其中(f(d))定义为(d)唯一分解后的最大指数幂，如(f(2^33^55^4) = 5,f(17^43^{18})=18)。
这个题是真的有意思。
考虑唯一分解：(T=p_1^{c_1}p_2^{c_2}...p_k^{c_k})，(d=p_1^{b_1}p_2^{b_2}...p_k^{b_k})。
显然(mu(frac{T}{d})=0)的项没有贡献，所以有贡献的项一定满足(c_i-b_ileq 1) 。
若存在(c_i < c_j)，则(b_i leq b_j) 。
此时(f(d))的取值与(b_i)的取值无关，而(c_i-b_i=0)或(1)时在(mu(frac{T}{d}))中的贡献恰好相反。
所以这种情况下存在对称性，即(sum_{d|T} mu(frac{T}{d}) f(d) = 0) 。
若(c_1=c_2=...c_k=c)，若存在(b_i<b_j)，则类似上面的对称性，贡献会为(0)。
唯一不存在对称性的情况是(b_1=b_2=...b_k=c-1)，此时(f(d))相比其反面少(1)。
故此时(sum_{d|T} mu(frac{T}{d}) f(d) = (-1)^{k+1})。
所以线性筛的同时记录最大指数幂(g)，通过判断(g[frac{i}{low(i)}]) 与 (g[low(i)p_j]) 是否相同进行转移。
[CQOI2017] 小Q的表格
两句话题意：给定一张(n imes n)的表格，每个位置有一个值(f(a,b))，满足：
对于正整数(a,b)，有(f(a,b)=f(b,a))且(bf(a,a+b)=(a+b)f(a,b))。
初始(f(a,b)=ab)。现在有(m)次操作((a,b,x,k))，
每次操作你需要将(f(a,b))改为(x)，并修改整个表格使得表格合法，
在修改完后，你需要输出前(k)行前(k)列表格中的数字之和，数据范围(nleq 10^6,mleq 10^4)。
首先把条件化为(frac{f(a,b)}{ab} = frac{f(a,a+b)}{a+b})。
这可以看作一个类欧过程，故(frac{f(a,a\%b)}{a(a\%b)} = frac{f(a,b)}{ab})，展开后有(frac{f(a,b)}{ab} = frac{f(d,d)}{d^2},d=gcd(a,b))
答案为(Ans = sum_{a=1}^Ksum_{b=1}^K f(a,b))。
带入上面的展开式后稍微化简一下有：(Ans = sum_{d=1}^K f(d,d) G(lfloor frac{K}{d}
floor))。
其中(G(n) = sum_{i=1}^n sum_{j=1}^n [gcd(i,j)=1]ij)，然后这题误导性最强的地方就在这里。
正常想法肯定是反演，然而如果去反演那就完蛋了到死也做不出来，正确姿势应该是：
(G(n) = sum_{i=1}^n i sum_{j=1}^n [gcd(i,j)=1]j = 1+2sum_{i=2}^n i(frac{varphi(i)}{2}i) = sum_{i=1}^n i^2 varphi(i)) 。
最后的问题在于维护(f(d,d))的前缀和，要求能够(O(sqrt{n}))修改，(O(1))回答。分块就行了。
[51NOD1847] 奇怪的数学题
一句话题意：求(sum_{i=1}^n sum_{j=1}^n sgcd(i,j)^k)，(nleq 10^9 , kleq 50)。
其中(sgcd(i,j))表示(i)和(j)的次小公因数。
其实这题还蛮简单的，毕竟太套路了，没啥思维含量......
显然(sgcd(i,j) = frac{gcd(i,j)}{p_{min}(gcd(i,j))})。
所以枚举(gcd(i,j)=d)，
列出式子后可以得到：(Ans = sum_{d=1}^{n} (frac{d}{p_{min}(d)})^k sum_{i=1}^{lfloor frac{n}{d}
floor}sum_{j=1}^{lfloor frac{n}{d}
floor} [gcd(i,j)=1])
然后用对称性稍微弄一下就可以得到：
爽！用min_25筛预先解决(sum_{i=1}^d(frac{i}{p_{min}(i)})^k)，然后对于(sum_{i=1}^n varphi(i))直接杜教筛即可。
[Luogu4240] 毒瘤之神的考验
一句话题意：(T)次询问(sum_{i=1}^n sum_{j=1}^m varphi(ij))。(n,mleq 10^5) ; (Tleq 10^4)。
常见套路先把(varphi(ij))写开可以得到：(Ans = sum_{d=1}^n frac{d}{varphi(d)} sum_{i=1}^n sum_{j=1}^n varphi(i) varphi(j) [gcd(i,j)=d])。
不要把(gcd=d)变为(gcd=1)，而是直接莫比乌斯反演可以得到：
其中(G(n , K) = sum_{i=1}^n varphi(iK)) 。
前面的一坨(F(i) = sum_{d|i} frac{d}{varphi(d)} mu(frac{i}{d}))显然是个迪利克雷卷积，线性筛出来就行了。
关于(G)如何求，妙哉妙哉！注意到(iKleq n)，所以暴力全算出来就行了，复杂度调和级数。
然后(Ans = sum_{i=1}^n F(i) G(lfloor frac{n}{i}
floor ,i) G(lfloor frac{m}{i}
floor ,i))，如何快速求答案？
又是妙哉妙哉，我们设(H(U,n,m) = sum_{i=1}^n F(i) G(n,i) G(m,i))。
然后我们设置一个阀值(B)，将(n,mleq B)的(H)全部预先算出来存到一个数组里去。
我们用预处理好(H)加上数论分块算好所有(n,mleq B)的答案。
对于(n,m > B) 的部分，因为有(frac{n}{i}> B)，所以(ileq lfloor frac{n}{B}
floor)不会很大，这部分直接暴力算。
那么此时复杂度变为了(O(B^2n + T(sqrt{n} + lfloor frac{n}{B}
floor )))，(B)取(T^{frac{1}{3}})左右即可得到可行的复杂度。
[NOI2016]循环之美
一句话题意： 求(K)进制下，(sum_{x=1}^n sum_{y=1}^m [)(frac{x}{y})为纯循环小数(])。(n,mleq 10^9),(Kleq 2000)。
小学"奥术"学过纯循环小数的处理：存在(t)，使得(frac{K^tx-x}{y} = k)。
所以(K^tx = ky + x)。所以(K^t \% y = 1)。
所以(Ans = sum_{x=1}^n sum_{y=1}^m [x perp y][Kperp y])，下面一题多解：
为了节省篇幅，设(f_s(n)=sum_{i=1}^n [iperp K] = lfloor frac{n}{K}
floor varphi(K) + brute(n \%K))
解1：(暴力拆([xperp y]))
(Ans = sum_{x=1}^n sum_{y=1}^n [Kperp y] sum_{d|gcd(x,y)} mu(d))
$Ans = sum_{d=1}^n mu(d) sum_{x=1}^{lfloor frac{n}{d} floor } sum_{y=1}^{lfloor frac{m}{d} floor} [K perp yd] ( )Ans = sum_{d=1}^n mu(d)[Kperp d] sum_{x=1}^{lfloor frac{n}{d} floor } sum_{y=1}^{lfloor frac{m}{d} floor} [K perp y] = sum_{d=1}^n mu(d) [K perp d] lfloor frac{n}{d} floor f_s(lfloor frac{m}{d} floor) ( )f(n,K) = sum_{d=1}^n mu(d)[Kperp d] = sum_{d=1}^n mu(d) sum_{s|K,s|d}mu(s)( )f(n,K) = sum_{s|K} mu(s) sum_{i=1}^{lfloor frac{n}{s} floor} mu(si) = sum_{s|K} mu(s)^2 sum_{i=1}^{lfloor frac{n}{s} floor} f(lfloor frac{n}{s} floor , s)( 递归处理即可，终态)f(n,1)$直接杜教筛。
QaQ一下，duang~~~
解2：(暴力拆([Kperp y]))
(g(n,m,K) = sum_{x=1}^n sum_{y=1}^m [xperp y] sum_{d|K,d|y} mu(d))
(g(n,m,K) = sum_{d|K} mu(d) sum_{x=1}^n sum_{i=1}^{lfloor frac{m}{d} floor} [xperp id])
(g(n,m,K) = sum_{d|K} mu(d) sum_{i=1}^{lfloor frac{m}{d} floor} sum_{x=1}^n [xperp i] [xperp d] = sum_{d|K} mu(d) g(lfloor frac{m}{d} floor ,n,d))
递归处理即可，终态(g(n,m,1))直接数论分块+杜教筛处理。
QwQ一下，duang~~~
解3：(某 高姓一本爷神仙 的做法)
拿着这道题去问(gzy)这题怎么算复杂度啊？min_25筛做是不是假的啊？
然后神仙就给了我这个神仙做法，
该做法时间复杂度仅(O(sqrt{n} + n^{frac{2}{3}}))，无论时间复杂度还是编程复杂度都吊打了一切题解。
回到解法一的中间：求(sum_{d=1}^n f(d) = sum_{d=1}^n mu(d) [Kperp d])。
我们构造函数(g(d) = [dperp K])，(f,g)都积性，故用(f(d))与(g(d))构造迪利克雷卷积。
(sum_{i=1}^n h(i) = sum_{i=1}^n sum_{d|i} f(d) g(frac{i}{d}) = sum_{i=1}^n sum_{d|i} mu(d) [Kperp d][Kperp frac{i}{d}])
(sum_{i=1}^n h(i) = sum_{i=1}^n sum_{d|i} mu(d) [K perp i] = sum_{i=1}^n [Kperp i] sum_{d|i} mu(d))。
(sum_{i=1}^n h(i) = sum_{i=1}^n [Kperp i][i=1] = sum_{i=1}^n [i=1])。
故(h(i) = [i=1])，写完整：(sum_{i=1}^n [i=1] = sum_{i=1}^n sum_{d|i} mu(d) [Kperp d][Kperp frac{i}{d}])
所以直接杜教筛即可：(sum_{i=1}^n f(i) = 1 - sum_{i=2}^n [iperp K]sum_{j=1}^{lfloor frac{n}{i} floor} f(j))。
这个解法真的太妙了！这构造真的神了，不管你怎么觉得，反正我是当场直接给跪了。