自动搬运

查看原文

来自洛谷，原作者为

	滑大稽 这个家伙不懒。้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็什么都留下了

搬运于2025-08-24 22:00:17，当前版本为作者最后更新于2021-02-02 21:06:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}