等腰直角三角形 题解

$\begin{aligned}\sum\limits_{i=1}^n\varphi(ki)&=\varphi(k)\sum\limits_{i=1}^n\frac{\varphi(i)\gcd(i,k)}{\varphi(\gcd(i,k))}\\&=\varphi(k)\sum\limits_{d\mid k}\frac{d}{\phi(d)}\sum\limits_{i=1}^n\varphi(i)[\gcd(i,k)=d]\\&=\varphi(k)\sum\limits_{d\mid k}\frac{d}{\varphi(d)}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(id)\sum\limits_{e\mid i,e\mid\frac{k}{d}}\mu(e)\\&=\varphi(k)\sum\limits_{e\mid k}\mu(e)\sum\limits_{d\mid{\frac{k}{e}}}\frac{d}{\varphi(d)}\sum\limits_{i=1}^{\lfloor\frac{n}{de}\rfloor}\varphi(ide)\\&=\varphi(k)\sum\limits_{T\mid k}\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\sum\limits_{d\mid T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})\end{aligned}$ 设 $\begin{aligned}S(n,k)=\sum\limits_{i=1}^n\varphi(ik),F(n)=\sum\limits_{d\mid n}\frac{d}{\varphi(d)}\mu(\frac{n}{d})\end{aligned}$ 则有 $\begin{aligned}S(n,k)=\varphi(k)\sum\limits_{T\mid k}F(T)S(\left\lfloor\frac{n}{T}\right\rfloor,T)\end{aligned}$ 提出T=1的部分杜教筛，其他部分递归暴力算. 关于$F$，显然这是个积性函数，并且可以发现 $F(p^k)=\begin{cases}1&k=0\\\frac{1}{p-1}&k=1\\0&k>1\end{cases}$ 处理逆元可能会被$mod\mid(p-1)$的情况卡掉，当然事实上我没有找到这样子的$p$... 推荐的做法是记录分母并用$\varphi(k)$除以这个东西(显然这样子是可以整除的). 然后所有k的因子的$\varphi$和$F$的分母都可以通过对k分解质因数$O(d(k)\log k)$预处理出来. 剩下的复杂度就比较玄学...首先要聪明点，只枚举使$F$非0的约数，然后我也不知道怎么算了.反正是$\Omega(n^{\frac{2}{3}})$，根据观察$k$的影响并不大.....k为前10个素数之积的时候也只能使这个东西达到 $7e5$.....