P4449 于神之怒加强版解题报告

解题报告

备注：$\mathbb{P}$为质数集，$\mathbb{N^+}$为自然数集。

P4449 于神之怒加强版解题报告：

更好的阅读体验

题意：给定$T$与$k$，后有$T$组数据给定$n$和$m$，求$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k$。数据范围：$1\leqslant T\leqslant 2\times 10^3$，$1\leqslant n,m,k\leqslant 5\times 10^6$。

我们可以先给原式变换一下形式（以下默认$n\leqslant m$）：
$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k$
首先套路性地枚举$\gcd$：$\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m d^k[\gcd(i,j)==d]$（中括号内的是一个有点像$bool$的东西）
可以发现造成贡献的都是$\gcd(i,j)==d$的$(i,j)$，那么$i$和$j$肯定是$d$的倍数，我们就将$i$和$j$缩小$d$倍：$\sum_{d=1}^nd^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)==1]$
然后莫比乌斯反演（$\sum_{d\mid n}\mu(d)=[n==1]$）：$\sum_{d=1}^nd^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{r\mid\gcd(i,j)}\mu(r)$
由于$r$是$\gcd(i,j)$的因数，因此$r$一定是$i$和$j$的公因数，仿照上面，我们将$i$和$j$缩小$r$倍（顺便改变一下运算顺序）：$\sum_{d=1}^nd^k\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d\cdot r}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d\cdot r}\rfloor}\mu(r)$
稍微做一下变形：$\sum_{d=1}^n d^k\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\cdot\lfloor\frac{n}{d\cdot r}\rfloor\cdot\lfloor\frac{m}{d\cdot r}\rfloor$
然后我们可以设$t=d\cdot r$（这样我们可以把$d$的枚举变为枚举$t$的因数），然后可以得到：$\sum_{t=1}^n\sum_{d\mid t} d^k\cdot\mu(\frac{t}{d})\cdot\lfloor\frac{n}{t}\rfloor\cdot\lfloor\frac{m}{t}\rfloor$
设$f(x)=\sum_{d\mid x}d^k\cdot\mu(\frac{x}{d})$，则原式化为：$\sum_{t=1}^nf(t)\cdot\lfloor\frac{n}{t}\rfloor\cdot\lfloor\frac{m}{t}\rfloor$
然后我们用整除分块可以做到$O(\sqrt{n})$的时间，于是我们的目标转移到如何线性筛预处理$f$函数：
由两个积性函数（$id_k(x)=x^k$与$\mu(x)=\cases{1,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x=1\\(-1)^s,\ \ \ \ \ \ \ x=p_1\cdot p_2\cdots p_s(\forall_{1\leqslant i\leqslant x,1\leqslant j\leqslant x,i\ne j}p_i\ne p_j)\\0,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ otherwise}$）
的狄利克雷卷积也是一个积性函数，我们可以构造$x$的标准分解$x=\prod_{i=1}^s p_i^{k_i}$得到$f(x)=\prod_{i=1}^s f(p_i^{k_i})$，于是我们转而计算一个质数的幂次方。
由莫比乌斯函数的性质（如果一个数$x$是一个完全平方数的倍数，那么$\mu(x)=0$，这是莫比乌斯函数的定义）可得，当$p\in\mathbb{P}$，$c\in\mathbb{N^+}$：$f(p^c)=\sum_{d\mid p^c} d^k\cdot\mu(\frac{p^c}{d})=\sum_{d\mid p^c,\frac{p^c}{d}\nmid z^2(z\in\mathbb{N})}d^k\cdot\mu(\frac{p^c}{d})\\=(p^{c-1})^k\cdot\mu(p)+(p^c)^k\cdot\mu(1)=p^{c\cdot k}-p^{(c-1)\cdot k}=p^{(c-1)\cdot k}\cdot(p^k-1)$
因此很显然有：$f(p^{c+1})=p^{c\cdot k}\cdot(p^k-1)=p^k\cdot p^{(c-1)\cdot k}\cdot(p^k-1)=f(p^c)\cdot p^k$
然后我们考虑求$f(p)$，发现$f(p)=\sum_{d\mid x}d^k\cdot\mu(\frac{x}{d})=1^k\cdot\mu(p)+p^k\cdot\mu (1)=p^k-1$
最后，我们讨论一下如何线性筛（求$f(x\cdot y)$，$x\in\mathbb{N^+}$，$y\in\mathbb{P}$）：
当$y\mid x$时，取$x$中$y$的幂次$c$，则由$f$的积性有$f(x\cdot y)=f(\frac{x\cdot y}{y^{c+1}})\cdot f(y^{c+1})$
由上文求出的$f(p^{c+1})=f(p^c)\cdot p^k$得再用$f$的积性合并得：$f(x\cdot y)=f(\frac{x}{y^c})\cdot f(y^c)\cdot y^k=f(\frac{x}{y^c}\cdot y^c)\cdot y^k=f(x)\cdot y^k$
当$y\nmid x$时，直接由$f$的积性可得$f(x\cdot y)=f(x)\cdot f(y)=f(x)\cdot f(y)$
综上所述$f(x\cdot y)=\cases{f(x)\cdot y^k,\ \ \ \ \ y\mid x\\f(x)\cdot f(y),\ \ y\nmid x}$
故线性筛+数论分块即可。

代码：

#include<stdio.h>
const long long maxn=5000005,mod=1000000007;
long long i,j,k,m,n,T,cnt,l,r,ans;
long long a[maxn],p[maxn],f[maxn],pf[maxn];
inline long long min(long long a,long long b){
    return a<b? a:b;
}
long long ksm(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod,b>>=1;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&T,&k);
    p[1]=f[1]=1;
    for(i=2;i<maxn;i++){
        if(p[i]==0)
            a[++cnt]=i,f[i]=(ksm(i,k)-1+mod)%mod;
        for(j=1;j<=cnt;j++){
            if(i*a[j]>=maxn)
                break;
            p[i*a[j]]=1;
            if(i%a[j]==0){
                f[i*a[j]]=f[i]*ksm(a[j],k)%mod;
                break;
            }
            f[i*a[j]]=f[i]*f[a[j]]%mod;
        }
    }
    for(i=1;i<maxn;i++)
        pf[i]=pf[i-1]+f[i];
    while(T--){
        scanf("%lld%lld",&n,&m);
        l=1,ans=0;
        while(l<=min(n,m)){
            r=min(n/(n/l),m/(m/l));
            ans=((ans+(pf[r]-pf[l-1]+mod)%mod*(n/l)%mod*(m/l)%mod)%mod+mod)%mod;
            l=r+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}