题解 P4449 【于神之怒加强版】

· · 题解

Update on 2021.2.4：修复了一些小错误

Update on 2021.9.1：再学线筛积性函数，补充解释，看的更清楚 （可能吧）。

Update on 2021.9.2：新增关于 G 函数的另一种筛法。

题外话：我研究了一下午题解终于搞懂了这道题，为了避免他人像我一样重(zhou)蹈(ma)覆(ti)辙(jie)，准备把我所理解的所有有关这道题的全部写出来。

首先，这个题目要求我们求这样一个式子：

\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k

一看到 \gcd，就可以很明显地感觉到，这是道莫反的题。

于是，我们开始按照莫反的思维推式子。

设

f(k)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] F(k)=\sum_{i=1}^n\sum_{j=1}^m[k|\gcd(i,j)]

其中

F(k)=\sum_{i=1}^{\lfloor \frac n k \rfloor}\sum_{j=1}^{\lfloor \frac m k \rfloor}1=\lfloor \frac n k \rfloor * \lfloor \frac m k \rfloor

然后就可以得到

F(k)=\sum_{k|d}f(d)

根据反演，就可以知道

f(k)=\sum_{k|d}\mu(\frac d k)* F(d)=\sum_{k|d}\mu(\frac d k)* \lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor

那么答案：

ans=\sum_{i=1}^{min(n,m)}i^k* f(i)=\sum_{i=1}^{min(n,m)}i^k* \sum_{i|d}\mu(\frac d i)* \lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor

其中 i^k 可以提到和号里面，\lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor 可以提到和号外面，就成了：

ans=\sum_{i=1}^{min(n,m)}\lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor* \sum_{i|d}\mu(\frac d i)* i^k

然后可以改一下和号的顺序:

ans=\sum_{d=1}^{min(n,m)} \lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor*\sum_{i|d} \mu(\frac d i)* i^{k}

这一切看起来都是那么的和谐，前面可以用整除分块搞掉。

这题，要切掉了吧？

“好水啊”你心里暗自感叹着。

可是，当你注意后面那一坨以后，你可能会直接懵掉。

你尝试把他变成 \varphi，但你发现答案成了这样：

ans=\sum_{d=1}^{min(n,m)} \lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor* \varphi(d)\sum_{i|d} i^{k-1}

后面这一坨还是搞不出来，不然 O(n*\sqrt n) 的预处理拿点分？

可是你又不甘心。

我们发现后面的那一坨是一个卷积的形式，并且两个函数均为积性函数，所以卷起来也是积性函数。考虑线性筛。

设：

g(x)=x^k G(n)=\sum_{i|n}g(i)* \mu(\frac n i)

那么答案就成了：

ans=\sum_{d=1}^{min(n,m)}G(d)* \lfloor \frac n d \rfloor * \lfloor \frac m d \rfloor

可是，G 又怎么求？

(update的另一种求法在第一份代码后面)

就是这个问题，困扰我许久，翻遍了所有题解，才总结出这个自认为易懂一点的解释：

先扔结论：

G(a* b)=G(a)* G(b)(\gcd(a,b)=1) G(a* b)=G(a)* b^k(\gcd(a,b) \ne 1\land b\in\mathbb P)

首先第一个式子应该很好证明吧：

根据定义易得，g,\mu 函数都为积性函数。而 G=g*\mu，所以根据狄利克雷卷积易知，G 也为积性函数，所以第一个式子得证。

关键就是第二个式子怎么证，证了就可以在线性筛的时候处理了，但它的证明也困扰了我一个多小时。

首先设:

a=p_1^{c_1}* p_2^{c_2} * p_3^{c_3}...* p_k^{c_k}(b\in \{p_i\})

注意到 b\in \{p_i\} 的条件是一定满足的，因为 b 是一个质数，并且 \gcd(a,b) \ne 1 。而这个条件在后面证明时会用到。

根据 G 是积性函数可知：

G(a)=\prod_{i=1}^kG(p_i^{c_i})

然后设 p_t=b（前后呼应），就可以得到如下式子：

\frac{G(a* b)}{G(a)}=\frac{\prod_{i=1}^kG(p_i^{c_i+[i=t]})}{\prod_{i=1}^kG(p_i^{c_i})}=\frac{G(p_t^{c_t+1})}{G(p_t^{c_t})}

这里解释一下，因为只有当 i=t 时分子分母的值才不同，其他的都可以约分约掉，所以可以约分成后面那个样子。

再看一下该怎么化简。尝试把 G 展开。

G(p_i^{c_i})=\sum_{j=0}^{c_i}g(p_i^{j})* \mu(p_i^{c_i-j})

这里是对于任意一个质数的 n 次幂的 G 函数值而言的。

然后我们发现，只有当 c_i-j \le 1 时 \mu(p_i^{c_i-j})\ne0（根据莫比乌斯函数的定义）

\therefore G(p_i^{c_i})=g(p_i^{c_i})-g(p_i^{c_i-1})

然后就可以带回原式了：

\frac{G(a* b)}{G(a)}=\frac{g(p_t^{c_t+1})-g(p_t^{c_t})}{g(p_t^{c_t})-g(p_t^{c_t-1})}=\frac{p_t^{(c_t+1)* k}-p_t^{c_t* k}}{p_t^{c_t* k}-p_t^{(c_t-1)* k}}=p_t^k=b^k

第二个式子也就证明出来了。

这里总结一下做法，先用线性筛把 G 函数的值证明出来，预处理一下前缀和，这里复杂度可以认为是 O(n) 的。（只在质数处跑了qpow，质数数量不多，所以这个 \log 对于复杂度没影响。）（质数和质数幂的数量乘上 \log 10^9+7 大概是 2\times n 的样子）

然后对于每一组询问，跑一次整除分块，单次复杂度 O(\sqrt n)，t 组复杂度就是 O(t*\sqrt n)。

总复杂度 O(n+t*\sqrt n)，可以通过此题。

请别介意我巨丑的代码：

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=5e6+5,mod=1e9+7;
int g[N],pri[N],sum[N];
bool v[N];
inline int read()
{
    char h=getchar();
    int y=0,q=1;
    while(h<'0'||h>'9'){if(h=='-')q=-1;h=getchar();}
    while(h>='0'&&h<='9'){y=y*10+h-'0';h=getchar();}
    return y*q;
}
inline int qpow(int a,int b)
{
    int j=1;
    while(b)
    {
        if(b&1)(j*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return j;
}
inline void init(int k)
{
    g[1]=1;
    int tot=0;
    for(int i=2;i<N;i++)
    {
        if(!v[i]){pri[++tot]=i;g[i]=(qpow(i,k)-1+mod)%mod;}
        for(int j=1;j<=tot&&pri[j]*i<N;j++)
        {
            v[pri[j]*i]=1;
            if(i%pri[j]==0)
            {
                g[pri[j]*i]=(g[i]*((g[pri[j]]+1)%mod))%mod;//g[pri[j]]+1=pri[j]^k
                break;
            }
            g[pri[j]*i]=(g[i]*g[pri[j]])%mod;
        }
    }
    for(int i=1;i<N;i++)sum[i]=(sum[i-1]+g[i])%mod;
}
inline int f(int a,int b)
{
    int n=min(a,b),ans=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(a/(a/l),b/(b/l));
        ans=(ans+(sum[r]-sum[l-1])*(a/l)%mod*(b/l)%mod+mod)%mod;
    }
    return ans;
}
signed main()
{
    int t=read(),k=read();
    init(k);
    while(t--)
    {
        int n=read(),m=read();
        printf("%lld\n",f(n,m));
    }
}

update:

我们发现，上面的求解证明有点复杂。作为一名专业的懒癌oier，肯定要用某个特定的规律来做这种题。

G(n)=\sum_{i|n}g(i)* \mu(\frac n i)

首先，对于质数，我们一般很好求它的值，就直接算了。

然后对于筛那部分，假如 pri[j]\nmid i，则他们是互质的，G[i* pri[j]]=G[i]* G[pri[j]]。

然后我们就考虑不互质的情况了。我们尝试把 i 中的 pri[j] 全部提出来。所以记录 ti[i] 为 i 中最小素因子的出现次数，t[i] 为最小素因子的 ti[i] 次方。则有 G[i* pri[j]]=G[\frac i {t[i]}]* G[pri[j]* t[i]]。

但是我们发现，对于 i* pri[j] 是一个质数的若干次幂的情况，它可能会自摸。比如 i=2,pri[j]=2，我们可以得到关于 G[4] 的所谓表达式：G[4]=G[1]* G[4]。这就有问题了。所以我们对于质数若干次幂特殊考虑下。设 i* pri[j]=p^b。因为右边是 \mu，所以只会有 g(p^b)* \mu(1)+g(p^{b-1})* \mu(p) 有贡献，展开即为 p^{bk}-p^{(b-1)k}。也就考虑完了。

复杂度仍然为 O(n+t*\sqrt n)。但是因为筛的位置在质数处和质数幂处跑了qpow，所以常数略大。但因为质数和质数幂数量较小，不会影响筛总体 O(n) 的复杂度。（质数和质数幂的数量乘上 \log 10^9+7 也大概是 2\times n 的样子）

上一下筛的代码就行了：

inline void init(int k)
{
    g[1]=1;
    int tot=0;
    for(int i=2;i<N;i++)
    {
        if(!v[i]){pri[++tot]=i;g[i]=(qpow(i,k)-1+mod)%mod;t[i]=i;ti[i]=1;}
        for(int j=1;j<=tot&&pri[j]*i<N;j++)
        {
            v[pri[j]*i]=1;
            if(i%pri[j]==0)
            {
                t[i*pri[j]]=t[i]*pri[j];
                ti[i*pri[j]]=ti[i]+1;
                if(t[i]==i)
                {
                    g[pri[j]*i]=qpow(pri[j],(ti[i]+1)*k)-qpow(pri[j],ti[i]*k);
                    if(g[pri[j]*i]<0)g[pri[j]*i]+=mod;
                }
                else
                {
                    g[i*pri[j]]=1ll*g[i/t[i]]*g[t[i]*pri[j]]%mod;
                }
                break;
            }
            g[pri[j]*i]=(g[i]*g[pri[j]])%mod;
            t[i*pri[j]]=pri[j];ti[i*pri[j]]=1;
        }
    }
    for(int i=1;i<N;i++)sum[i]=(sum[i-1]+g[i])%mod;
}