这道反演题，真牛逼。
以下用$B$代表伯努利数，$l*g=f$代表狄利克雷卷积,先推式子。
对于给出的$n,x,y$求一百组数据的$ans$
$egin{array}{rcl} ans & = & sumlimits_{i=1}^ngcd(i,n)^xlcm(i,n)^yend{array}$
$egin{array}{rcl} & = & sumlimits_{i=1}^ngcd(i,n)^xfrac{(in)^y}{gcd(i,n)^y}end{array}$
$egin{array}{rcl} & = & sumlimits_{i=1}^ngcd(i,n)^{x-y}(in)^yend{array}$
$egin{array}{rcl} & = & n^ysumlimits_{i=1}^ni^ygcd(i,n)^{x-y}end{array}$
$egin{array}{rcl} & = & n^ysumlimits_{d|n}d^{x-y} sum limits_{i=1}^{lfloor frac{n}{d} floor} (id)^y[gcd(i,lfloorfrac{n}{d} floor)=1]end{array}$
$egin{array}{rcl} & = & n^ysumlimits_{d|n}d^xsumlimits_{i=1}^{lfloor frac{n}{d} floor}i^ysumlimits_{t|gcd(i,lfloor frac{n}{d} floor)}mu(t)end{array}$
$egin{array}{rcl} & = & n^ysumlimits_{d|n}d^xsumlimits_{t|lfloorfrac{n}{d} floor}mu(t)t^ysumlimits_{i=1}^{lfloorfrac{n}{td} floor}i^yend{array}$
$egin{array}{rcl}sumlimits_{i=0}^{lfloorfrac{n}{td} floor}i^y & = & frac{1}{y+1}sumlimits_{i=0}^yC_{y+1}^iB_i(lfloorfrac{n}{td} floor)^{y-i+1}end{array}$
$egin{array}{rcl}R_i & = & frac{C_{y+1}^iB_i}{y+1}end{array}$
$egin{array}{rcl}ans & = & n^ysumlimits_{d|n}d^xsumlimits_{t|lfloorfrac{n}{d} floor}mu(t)t^ysumlimits_{i=0}^yR_i(lfloorfrac{n}{td} floor)^{y-i+1}end{array}$
$egin{array}{rcl} & = & sumlimits_{i=1}^yR_in^ysumlimits_{d|n}d^xsumlimits_{t|lfloorfrac{n}{d} floor}mu(t)t^y(lfloorfrac{n}{td} floor)^{y-i+1}end{array}$
$egin{array}{rcl}f_{i,x,y}(n) & = & n^ysumlimits_{d|n}d^xsumlimits_{t|lfloorfrac{n}{d} floor}mu(t)t^y(lfloorfrac{n}{td} floor)^{y-i+1}end{array}$
分析$f_{i,x,y}(n)$。
$egin{array}{rcl}l(x) & = & mu(x)x^y end{array}$
$egin{array}{rcl}q_r(x) & = & x^rend{array}$
$l,q$ 均为积性函数。
$egin{array}{rcl} g(n) & = & sumlimits_{d|n}mu(d)d^yq(lfloorfrac{n}{d} floor)end{array}$
$egin{array}{rcl}g(n) & = & l(n)*q(n)end{array}$
也为积性函数。
$egin{array}{rcl}f(n) & = & sumlimits_{d|n}q(d)g(lfloorfrac{n}{d} floor) \ & = & q(n)*g(n) end{array}$
所以$f_{i,x,y}(n)$是积性函数。
$egin{array}{rcl}ans & = & sumlimits_{i=0}^yR_if_{i,x,y}(n)end{array}$
$n$为$1e18$考虑用$O(n^{1/4})$的$Pollard_Rho$算法对$n$进行质因分解。
$n=\_p^c$
$egin{array}{rcl}f_{i,x,y}(p^c) & = & p^{cy}sumlimits_{d|p^c}sumlimits_{t|lfloorfrac{p^c}{d} floor}mu(t)t^y(lfloorfrac{p^c}{td} floor)^{y-i+1}end{array}$
$egin{array}{rcl} & = & p^{cy}sumlimits_{j=0}^cp^{jx}sumlimits_{k=0}^{c-j}mu(p^k)p^{ky}(p^{c-j-k})^{y-i+1}end{array}$
当k=1或者0的时候，莫比乌斯函数不为0。
$egin{array}{rcl} & = & p^{cy}sumlimits_{j=0}^c p^{jx}[(p^{c-j})^{y-i+1}-p^y(p^{c-j-1})^{y-i+1}]end{array}$
问题得到解决。
知识点：
莫比乌斯反演
狄利克雷卷积
积性函数
自然数幂和
伯努利数
$Miller\_Rabin$素数测试
$Pollard\_Rho$质因数分解
费马小定理
二次初探原理
生日悖论
有兴趣的可以尝试一下，是道好题。