bzoj4407 于神之怒加强版

题意:求$\sum _{i=1}^n \sum _{j=1}^m (i,j)^k \mod (10^9+7)$。

多组数据($T\leq 2000​$),$n,m,k \leq 5000000​$。

题解:

按照一般的反演套路有

$$\sum_{i=1}^n \sum _{j=1}^m (i,j)^k = \sum _{d=1}^{n}d^k \sum_{x=1}^{\lfloor n/d \rfloor} \mu(x) \lfloor \frac{n}{xd} \rfloor \lfloor \frac{m}{xd} \rfloor$$

如果不是多组询问,设$f(d)=\sum_{x=1}^{\lfloor n/d \rfloor} \mu(x) \lfloor \frac{n}{xd} \rfloor \lfloor \frac{m}{xd} \rfloor$,当$\lfloor n/d \rfloor$确定时$f$的值一定,所以按$\lfloor n/d \rfloor$的值先对前面的分块(至于$d^k$可以$nlogn$预处理并且求前缀和),确定了一个$\lfloor n/d \rfloor$的值后再对$f(d)$中的$\lfloor \frac{n}{xd} \rfloor ,\lfloor \frac{m}{xd} \rfloor$进行分块求解。复杂度$O(nlogn+\sqrt{n}\cdot \sqrt{n})$。

对于多组询问,设$T=xd$,则原式化为

$$\sum _{d=1}^n \sum _{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \mu(\frac{T}{d})= \sum _{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum _{d|T} \mu(\frac{T}{d}) d^k$$

设$g(T)= \sum _{d|T} \mu(\frac{T}{d}) d^k$

由莫比乌斯反演的性质,因为$\mu(x)$,${d^k}$均为积性函数,所以$g(T)$也为积性函数。设$T=\prod {p_i}^{x_i}$

$$g(T)=\prod _{p_i} g(p_i^{x_i})$$又因为$\mu(x)$只要有平方因子就会为$0$,所以

$$ g(T)=\prod _{p_i} g(p_i^{x_i}) =\prod_{p_i}({p_i}^{x_ik}-{p_i}^{(x_i-1)k})=\prod_{p_i}{p_i}^{(x_i-1)k}(p_i^k-1)$$

可以线性筛出$g(T)$,然后求一个前缀和,对于前面的部分依旧分块求解,复杂度$O(n+T\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
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000000+5;
const int mo=(int)1e9+7;
int pri[maxn],cnt=0,g[maxn],sum[maxn];
bool vis[maxn];
int quickpow(int x,int k)
{
int ret=1;
while(k>0) {
if(k&1) ret=1ll*ret*x%mo;
x=1ll*x*x%mo;
k>>=1;
}
return ret;
}
void sieve(int k)
{
g[1]=1;
for(int i=2;i<maxn;i++) {
if(!vis[i]) pri[++cnt]=i,g[i]=(quickpow(i,k)-1+mo)%mo;
for(int j=1;j<=cnt && pri[j]*i<maxn;j++) {
int t=pri[j]*i;
vis[t]=true;
if(i%pri[j]==0) {g[t]=1ll*g[i]*(g[pri[j]]+1)%mo;break;}
g[t]=1ll*g[i]*g[pri[j]]%mo;
}
}
for(int i=1;i<maxn;i++) sum[i]=(sum[i-1]+g[i])%mo;
}
int main()
{
int T,K,n,m;
scanf("%d%d",&T,&K);
sieve(K);
for(int z=0;z<T;z++) {
scanf("%d%d",&n,&m);
int d=1,las=1,res=0;
if(n>m) swap(n,m);
d=1,las=1,res=0;
while(d<=n) {
las=min((n/(n/d)),(m/(m/d)));
res=(res+1ll*(n/d)*(m/d)%mo*1ll*((sum[las]-sum[d-1]+mo)%mo)%mo)%mo;
d=las+1;
}
printf("%d\n",res);
}
return 0;
}