等腰直角三角形 题解

2019-07-11 11:50:16


$\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$.....