2020 Multi-University Training Contest 6---- 6833、A Very Easy Math Problem（莫比乌斯函数）

题面：

题意：
求 $\sum_{a_{1} = 1}^{n} \sum_{a_{2} = 1}^{n} . . . \sum_{a_{x} = 1}^{n} (\prod_{j = 1}^{x} a_{j}^{k}) f (g c d (a_{1}, a_{2}, . . ., a_{x})) * g c d (a_{1}, a_{2}, . . ., a_{x})$ 。

题解：
官方题解给定了 $O (n l o g n)$ 预处理， $O (\sqrt{n})$ 回答单次询问的解法。

只会 $O (n \sqrt{n} + T \sqrt{n})$ 的解法，下面介绍 $O (n \sqrt{n} + T \sqrt{n})$ 的解法。

$a n s = \sum_{a_{1} = 1}^{n} \sum_{a_{2} = 1}^{n} . . . \sum_{a_{x} = 1}^{n} (\prod_{j = 1}^{x} a_{j}^{k}) f (g c d (a_{1}, a_{2}, . . ., a_{x})) * g c d (a_{1}, a_{2}, . . ., a_{x})$

容易发现 $f (x) = μ (x)^{2}$ ，我们将 $f (x)$ 替换为 $μ (x)^{2}$
得到：

$a n s = \sum_{a_{1} = 1}^{n} \sum_{a_{2} = 1}^{n} . . . \sum_{a_{x} = 1}^{n} (\prod_{j = 1}^{x} a_{j}^{k}) μ (g c d (a_{1}, a_{2}, . . ., a_{x}))^{2} * g c d (a_{1}, a_{2}, . . ., a_{x})$

我们先枚举 $g c d$ :

$a n s = \sum_{d = 1}^{n} \sum_{a_{1} = 1}^{n} \sum_{a_{2} = 1}^{n} . . . \sum_{a_{x} = 1}^{n} (\prod_{j = 1}^{x} a_{j}^{k}) μ (d)^{2} * [g c d (a_{1}, a_{2}, . . ., a_{x}) = = d] * d$

那么有：

$a n s = \sum_{d = 1}^{n} d^{k x + 1} μ (d)^{2} \sum_{a_{1} = 1}^{n / d} \sum_{a_{2} = 1}^{n / d} . . . \sum_{a_{x} = 1}^{n / d} (\prod_{j = 1}^{x} a_{j}^{k}) [g c d (a_{1}, a_{2}, . . ., a_{x}) = = 1]$

根据 $[g c d (i, j) = 1] = <munder> \sum d ∣ g c d (i, j) </munder> μ (d)$ 有：

$a n s = \sum_{d = 1}^{n} d^{k x + 1} μ (d)^{2} \sum_{a_{1} = 1}^{n / d} \sum_{a_{2} = 1}^{n / d} . . . \sum_{a_{x} = 1}^{n / d} (\prod_{j = 1}^{x} a_{j}^{k}) <munder> \sum g ∣ g c d (a_{1}, a_{2}, . . ., a_{x}) </munder> μ (g)$

转换枚举顺序，先枚举 $g$ 得：

$a n s = \sum_{d = 1}^{n} d^{k x + 1} μ (d)^{2} \sum_{g = 1}^{n / d} μ (g) \sum_{a_{1} = 1}^{n / d} g ∣ a_{1} \sum_{a_{2} = 1}^{n / d} g ∣ a_{2} . . . \sum_{a_{x} = 1}^{n / d} g ∣ a_{x} (\prod_{j = 1}^{x} a_{j}^{k})$

化简之后得到：

$a n s = \sum_{d = 1}^{n} d^{k x + 1} μ (d)^{2} \sum_{g = 1}^{n / d} g^{k x} μ (g) \sum_{a_{1} = 1}^{(n / d) / g} \sum_{a_{2} = 1}^{(n / d) / g} . . . \sum_{a_{x} = 1}^{(n / d) / g} (\prod_{j = 1}^{x} a_{j}^{k})$

$a n s = \sum_{d = 1}^{n} d^{k x + 1} μ (d)^{2} \sum_{g = 1}^{n / d} g^{k x} μ (g) \sum_{a_{1} = 1}^{(n / d) / g} a_{1}^{k} \sum_{a_{2} = 1}^{(n / d) / g} a_{2}^{k} . . . \sum_{a_{x} = 1}^{(n / d) / g} a_{x}^{k}$

其中 $d^{k x + 1}, μ (d)^{2}, g^{k x}, μ (g), \sum_{a_{1} = 1}^{(n / d) / g} a_{1}^{k} \sum_{a_{2} = 1}^{(n / d) / g} a_{2}^{k} . . . \sum_{a_{x} = 1}^{(n / d) / g} a_{x}^{k}$ 均可以预处理求出，时间复杂度 $O (n l o g n)$

对于外层求和 $\sum_{d = 1}^{n}$ ，我们可以分块去求 $\sum_{g = 1}^{n / d}$ 。
而对于 $\sum_{g = 1}^{n / d}$ ，我们又可以分块去求 $\sum_{a_{1} = 1}^{(n / d) / g} a_{1}^{k} \sum_{a_{2} = 1}^{(n / d) / g} a_{2}^{k} . . . \sum_{a_{x} = 1}^{(n / d) / g} a_{x}^{k}$ 。

这样的复杂度是 $O (T * \sqrt{n} \sqrt{n})$ 的。

但是仔细观察发现，对于 $\sum_{g = 1}^{n / d}$ ，我们分块去求 $\sum_{a_{1} = 1}^{(n / d) / g} a_{1}^{k} \sum_{a_{2} = 1}^{(n / d) / g} a_{2}^{k} . . . \sum_{a_{x} = 1}^{(n / d) / g} a_{x}^{k}$ 。对于所有的 $i \in [1, n], \sum_{g = 1}^{i}$ 全部求出来的时间复杂度是 $O (n \sqrt{n})$ 。所以我们只需要把这 $n$ 个状态记录下来，每个状态需要 $O (\sqrt{n})$ 求解。

这样总的时间复杂度是 $O (n \sqrt{n} + T \sqrt{n})$ 的。

代码：

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
//#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=10000100;
const int maxp=100100;
const int up=30;
int t,k,x,n;
int a[maxn],g[maxn],mu[maxn],mu2[maxn],d[maxn];
int cm[maxn],dp[maxn];
int prime[maxn],cnt=0;
bool ha[maxn];

int mypow(int a,ll b)
{
    b%=(mod-1);
    int ans=1;
    while(b)
    {
        if(b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}

void Mu(void)
{
    mu[1]=1;
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
        {
            mu[i]=-1;
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<maxn;i++)
    {
        d[i]=mypow(i,1ll*k*x+1);
        mu2[i]=mu[i]*mu[i];

        g[i]=mypow(i,1ll*k*x);

        cm[i]=(cm[i-1]+mypow(i,k))%mod;
        a[i]=mypow(cm[i],x);

        d[i]=(d[i-1]+mu2[i]*d[i])%mod;

        g[i]=(g[i-1]+mu[i]*g[i])%mod;

    }
}

int main(void)
{
    scanf("%d%d%d",&t,&k,&x);
    Mu();
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        scanf("%d",&n);;
        int ans=0,res=0;
        int up=0;
        for(int ld=1,rd;ld<=n;ld=rd+1)
        {
            rd=min(n,n/(n/ld));

            up=n/ld;
            if(dp[up]==-1)
            {
                res=0;
                for(int lg=1,rg;lg<=up;lg=rg+1)
                {
                    rg=min(up,up/(up/lg));
                    res=(res+1ll*(g[rg]-g[lg-1])*a[up/lg])%mod;
                }
                dp[up]=(res+mod)%mod;
            }

            ans=(ans+1ll*(d[rd]-d[ld-1])*dp[up])%mod;
        }
        printf("%d\n",(ans%mod+mod)%mod);
    }
    return 0;
}