洛谷4449 BZOJ4407 于神之怒加強版 莫比烏斯反演 線性篩

題目連結

題意：

給定 n , m , k n,m,k n,m,k，求 ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) k \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k ∑i=1n​∑j=1m​gcd(i,j)k，有 T T T組資料，每組資料的 k k k是相同的。 T &lt; = 2000 , n , m , k &lt; = 5000000 T&lt;=2000,n,m,k&lt;=5000000 T<=2000,n,m,k<=5000000。

題解：

顯然是要推式子的。

∑ i = 1 n ∑ j = 1 m g c d ( i , j ) k \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k i=1∑n​j=1∑m​gcd(i,j)k 我們枚舉 g c d ( i , j ) gcd(i,j) gcd(i,j) ∑ d = 1 m i n ( n , m ) d k ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] \sum_{d=1}^{min(n,m)}d^k\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d] d=1∑min(n,m)​dki=1∑n​j=1∑m​[gcd(i,j)=d] 我們利用莫比烏斯反演，設 f ( k ) = ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = k ] f(k)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k] f(k)=∑i=1n​∑j=1m​[gcd(i,j)=k]，設 g ( k ) = ∑ i ∗ k &lt; = m i n ( n , m ) f ( i ∗ k ) = ∑ i = 1 n ∑ j = 1 m [ k ∣ g c d ( i , j ) ] = ⌊ n k ⌋ ⌊ m k ⌋ g(k)=\sum_{i*k&lt;=min(n,m)}f(i*k)=\sum_{i=1}^n\sum_{j=1}^m[k|gcd(i,j)]=\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor g(k)=∑i∗k<=min(n,m)​f(i∗k)=∑i=1n​∑j=1m​[k∣gcd(i,j)]=⌊kn​⌋⌊km​⌋，由莫比烏斯反演可以得到 f ( k ) = ∑ i ∗ k &lt; = m i n ( n , m ) μ ( i ) g ( i ∗ k ) f(k)=\sum_{i*k&lt;=min(n,m)}\mu(i)g(i*k) f(k)=∑i∗k<=min(n,m)​μ(i)g(i∗k)

我們把 f ( d ) f(d) f(d)帶入 ∑ i ∗ d &lt; = m i n ( n , m ) μ ( i ) g ( i ∗ d ) \sum_{i*d&lt;=min(n,m)}\mu(i)g(i*d) ∑i∗d<=min(n,m)​μ(i)g(i∗d)可得

∑ d = 1 m i n ( n , m ) d k ∑ i ∗ d &lt; = m i n ( n , m ) μ ( i ) g ( i ∗ d ) \sum_{d=1}^{min(n,m)}d^k\sum_{i*d&lt;=min(n,m)}\mu(i)g(i*d) d=1∑min(n,m)​dki∗d<=min(n,m)∑​μ(i)g(i∗d) 由于 g ( k ) = ⌊ n k ⌋ ⌊ m k ⌋ g(k)=\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor g(k)=⌊kn​⌋⌊km​⌋ ∑ d = 1 m i n ( n , m ) d k ∑ i ∗ d &lt; = m i n ( n , m ) μ ( i ) ⌊ n i ∗ d ⌋ ⌊ m i ∗ d ⌋ \sum_{d=1}^{min(n,m)}d^k\sum_{i*d&lt;=min(n,m)}\mu(i)\lfloor\frac{n}{i*d}\rfloor\lfloor\frac{m}{i*d}\rfloor d=1∑min(n,m)​dki∗d<=min(n,m)∑​μ(i)⌊i∗dn​⌋⌊i∗dm​⌋ 把後面的 μ \mu μ提出來 ∑ i = 1 n μ ( i ) ∑ d = 1 ⌊ m i n ( n , m ) i ⌋ ⌊ n i ∗ d ⌋ ⌊ m i ∗ d ⌋ \sum_{i=1}^n\mu(i)\sum_{d=1}^{\lfloor\frac{min(n,m)}{i}\rfloor}\lfloor\frac{n}{i*d}\rfloor\lfloor\frac{m}{i*d}\rfloor i=1∑n​μ(i)d=1∑⌊imin(n,m)​⌋​⌊i∗dn​⌋⌊i∗dm​⌋ ∑ d = 1 m i n ( n , m ) ⌊ n d ⌋ ⌊ m d ⌋ ∑ i ∣ d i k μ ( ⌊ d i ⌋ ) \sum_{d=1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{i|d}i^k\mu(\lfloor\frac{d}{i}\rfloor) d=1∑min(n,m)​⌊dn​⌋⌊dm​⌋i∣d∑​ikμ(⌊id​⌋)

我們要整除分塊，就要算後面那一部分 ∑ i ∣ d i k μ ( ⌊ d i ⌋ ) \sum_{i|d}i^k\mu(\lfloor\frac{d}{i}\rfloor) ∑i∣d​ikμ(⌊id​⌋)的字首和。我們設 f ( n ) = ∑ d ∣ n d k μ ( ⌊ n d ⌋ ) f(n)=\sum_{d|n}d^k\mu(\lfloor\frac{n}{d}\rfloor) f(n)=∑d∣n​dkμ(⌊dn​⌋)，我們發現，兩部分都是積性函數，是以根據狄利克雷卷積的性質，卷起來仍然是積性函數，于是可以用線性篩來做。在目前數是質數的時候 f ( i ) = i − 1 f(i)=i-1 f(i)=i−1，這個算算就行了，就不解釋了。由于是積性函數，是以在兩個數互質的情況直接用兩個函數值相乘就行了。那麼剩下的就是 i = p i x i=p_i^x i=pix​的情況了。

f ( p i x ) = μ ( 1 ) ∗ ( p i x ) k + μ ( p i ) ∗ ( p i x − 1 ) k f(p_i^x)=\mu(1)∗(p_i^x)^k+\mu(p_i)∗(p_i^{x−1})^k f(pix​)=μ(1)∗(pix​)k+μ(pi​)∗(pix−1​)k，剩下項的 μ \mu μ都是 0 0 0。那麼對于一個質因數來說, f ( p i x ) f(p_i^x) f(pix​)變成 f ( p i x + 1 ) f(p_i^{x+1}) f(pix+1​)的影響就是在 f ( p i x + 1 ) f(p_i^{x+1}) f(pix+1​)的基礎上乘 p i k p_i^k pik​。這樣就可以線性篩了。

總複雜度 O ( n l o g n + T n ) O(nlogn+T\sqrt{n}) O(nlogn+Tn

​)。

代碼：

#include <bits/stdc++.h>
using namespace std;

const long long mod=1e9+7;
int T,k,n,m,cnt,vis[5000010];
long long f[5000010],s[5000010],ans,p[5000010];
inline long long ksm(long long x,long long y)
{
	long long res=1;
	while(y)
	{
		if(y&1)
		res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
inline void solve(int n)
{
	vis[1]=1;
	f[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!vis[i])
		{
			p[++cnt]=i;
			f[i]=(ksm(i,k)-1+mod)%mod;
		}
		for(int j=1;j<=cnt&&i*p[j]<=n;++j)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				f[i*p[j]]=f[i]*ksm(p[j],k)%mod;
				break;
			}
			f[i*p[j]]=f[i]*f[p[j]]%mod;
		}
	}
	for(int i=1;i<=n;++i)
	s[i]=(s[i-1]+f[i])%mod;
}
int main()
{
	scanf("%d%d",&T,&k);
	solve(5000000);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		ans=0;
		long long r;
		for(long long l=1;l<=min(n,m);l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			ans=(ans+(n/l)*(m/l)%mod*(s[r]-s[l-1]+mod)%mod)%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}