题目链接
题解
容易发现本题是 GCD SUM 的推广。
方法一
走莫比乌斯反演的路子，套路性的枚举 \(\gcd\) 的值。
$$ \begin{align} &\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \ldots \sum_{i_n=1}^{m}\gcd(i_1,i_2, \ldots i_n) \\ =&\sum_{d=1}^{m}d\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \ldots \sum_{i_n=1}^{m}[\gcd(i_1,i_2, \ldots i_n)=d] \\ =&\sum_{d=1}^{m}d\sum_{i_1=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{i_2=1}^{\lfloor \frac{m}{d} \rfloor} \ldots \sum_{i_n=1}^{\lfloor \frac{m}{d} \rfloor}[\gcd(i_1,i_2, \ldots i_n)=1] \\ =&\sum_{d=1}^{m}d\sum_{i_1=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{i_2=1}^{\lfloor \frac{m}{d} \rfloor} \ldots \sum_{i_n=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{t \mid i_1, t \mid i_2, \ldots , t \mid i_n}\mu(t) \\ =&\sum_{d=1}^{m}d\sum_{t=1}^{\lfloor \frac{m}{d} \rfloor}\mu(t)\lfloor \frac{m}{dt} \rfloor^n \\ =&\sum_{T=1}^{m}\lfloor \frac{m}{T} \rfloor ^n \sum_{d|T} d \mu(\frac{T}{d}) \\ =&\sum_{T=1}^{m}\lfloor \frac{m}{T} \rfloor ^n \varphi(T) \end{align} $$
看着挺烦人的，接下来我们有种更简单的方法。
方法二
根据 \(\sum_{d \mid n}\varphi(d)=n\) 的性质直接换掉 \(\gcd\)。
$$ \begin{align} &\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \ldots \sum_{i_n=1}^{m}\gcd(i_1,i_2, \ldots i_n) \\ =& \sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \ldots \sum_{i_n=1}^{m} \sum_{d \mid \gcd(i_1,i_2, \ldots i_n)}\varphi(d)\\ =& \sum_{d=1}^m \varphi(d)\sum_{i_1=1}^m[d \mid i_1]\sum_{i_2=1}^m[d \mid i_2] \ldots \sum_{i_n=1}^m[d \mid i_n]\\ =& \sum_{d=1}^m \varphi(d)\left \lfloor \frac{m}{d} \right \rfloor^n \end{align}$$
同样的结果，这个方法就比上面简洁多了。
最后直接用杜教筛计算即可。
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define N 20000000
using namespace std;
typedef unsigned long long ull;
ull phi[N+5];
int pri[N+5],cnt;
bool vis[N+5];
unordered_map<ull,ull> psum;
ull fpow(ull x,ull y)
{
ull ans=1;
while(y)
{
if(y&1)ans=ans*x;
x=x*x;
y>>=1;
}
return ans;
}
ull phi_sum(ull x)
{
if(x<=N)return phi[x];
if(psum.count(x))return psum[x];
ull res=(x&1)?(x+1)/2*x:x/2*(x+1);
for(ull l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
res-=(r-l+1)*phi_sum(x/l);
}
return psum[x]=res;
}
int main()
{
ull n,m,ans=0;
cin>>n>>m;
phi[1]=1;
for(int i=2;i<=N;i++)
{
if(!vis[i])phi[i]=i-1,pri[++cnt]=i;
for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]!=0)
phi[i*pri[j]]=phi[i]*phi[pri[j]];
else
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
}
}
for(int i=1;i<=N;i++)
phi[i]+=phi[i-1];
for(ull l=1,r;l<=m;l=r+1)
{
r=m/(m/l);
ans+=fpow(m/l,n)*(phi_sum(r)-phi_sum(l-1));
}
cout<<ans<<endl;
return 0;
}