bzoj 4407 于神之怒加强版

Posted on | Views:

莫比乌斯反演.

  • 假定 $n\leq m$ ,推式子.

  • 把后面那个 $\sum_{d|x} \mu(\frac x d) \cdot d^k$ 看做关于 $x$ 的函数 $f(x)$ ,它显然是个积性函数,因为可以看成 $\mu(x)$ 与 $x^k$ 的卷积.
  • 线性筛预处理出 $f(x)$ 的前缀和,然后整除分块计算即可.
  • 时间复杂度 $O(n+T\cdot \sqrt n)$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a+b>=P?a+b-P:a+b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=5e6+10;
int ism[MAXN],prime[MAXN],cnt=0,mu[MAXN],pw[MAXN];
int k,sum[MAXN],f[MAXN];
void init(int n)
{
	f[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!ism[i])
		{
			prime[++cnt]=i;
			pw[i]=fpow(i,k);
			f[i]=add(pw[i],P-1);
		}
		for(int j=1;j<=cnt && 1LL*i*prime[j]<=n;++j)
		{
			int x=i*prime[j];
			ism[x]=1;
			pw[x]=mul(pw[i],pw[prime[j]]);
			if(i%prime[j]==0)
			{
				f[x]=mul(f[i],pw[prime[j]]);
				break;
			}	
			f[x]=mul(f[i],f[prime[j]]);
		}
	}
	for(int i=1;i<=n;++i)
		sum[i]=add(sum[i-1],f[i]);
}
int n,m;
int main()
{
	int T=read();
	k=read();
	init(5000000);
	while(T--)
	{
		n=read(),m=read();
		if(n>m)
			swap(n,m);
		int ans=0;
		for(int l=1,r;l<=n;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			int tmp=mul(n/l,m/l);
			tmp=mul(tmp,add(sum[r],P-sum[l-1]));
			ans=add(ans,tmp);
		}
		printf("%d\n",ans);
	}
	return 0;
}