bzoj 4407 于神之怒加强版

莫比乌斯反演.

  • 假定 $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;
}