[loj 6491]简单的最大公约数

题目链接

https://loj.ac/problem/6491

题解

容易发现本题是 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;
}