BZOJ2705

题面传送门

一道有意思的Phi题。

考虑枚举N的约数k,令表示有多少

那么此时答案变为

因为,那么,即

由Phi的通式可以在根号范围内求解。复杂度这么爆炸的做法我也不知道怎么过的

分解质因数里的第个因子)