【bzoj4407】【于神之怒加强版】【莫比乌斯反演】

本文主要是介绍【bzoj4407】【于神之怒加强版】【莫比乌斯反演】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给下N,M,K.求

\sum i = 1 n \sum j = 1 m g c d (i, j) k m o d (109 + 7)

$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k mod (10^9+7)$
Input

输入有多组数据，输入数据的第一行两个正整数T,K，代表有T组数据，K的意义如上所示，下面第二行到第T+1行，每行为两个正整数N,M，其意义如上式所示。
Output

如题
Sample Input

1 2
3 3
Sample Output

20
HINT

1<=N,M,K<=5000000,1<=T<=2000
题解：
首先可以化成

\sum d = 1 n d k \sum i = 1 ⌊ n d ⌋ ⌊ n i d ⌋ ⌊ m i d ⌋ u (i)

$\sum_{d=1}^{n}d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor u(i)$
设T=i*d
则可以化成

\sum T = 1 n ⌊ n T ⌋ ⌊ m T ⌋ \sum d | T d k u (T d)

$\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}^{}d^ku(\frac{T}{d})$
设f(T)=

∑d|Tdku(Td) $\sum_{d|T}^{}d^ku(\frac{T}{d})$
只要求出f数组,处理每组查询就是o(

n√) $\sqrt n)$ 了。
考虑

dk $d^k$ 是积性函数,所以f(T)也是积性函数。
所以我们就可以在线筛中处理f数组。
然后搞个前缀和即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 5000010
#define P 1000000007 
#define LL long long
using namespace std;
int T,k,p[N],f[N],pos;
LL n,m,g[N],u[N],ans;
LL power(LL a,int b){LL ans;a%=P;for (ans=1;b;a=a*a%P,b>>=1) if (b&1) ans=ans*a%P;return ans;
}
void pre(){u[1]=1;g[1]=1;for (int i=2;i<=n;i++){if (!f[i]){p[++p[0]]=i;u[i]=-1;g[i]=(power(i,k)-1+P)%P;}for (int j=1;j<=p[0]&&i*p[j]<=n;j++){f[i*p[j]]=1; if (i%p[j]==0){g[i*p[j]]=g[i]*power(p[j],k)%P;break;}u[i*p[j]]=-u[i];g[i*p[j]]=(g[i]*g[p[j]])%P;} }for (int i=1;i<=n;i++) g[i]=(g[i]+g[i-1])%P;
}
int main(){scanf("%d%d",&T,&k);n=N-10;pre();while (T--){scanf("%d%d",&n,&m);if (n>m) swap(n,m);ans=0;pos=0; for (int i=1;i<=n;i=pos+1){pos=min(n/(n/i),m / (m / i));ans+=(LL)(n / i)*(LL)(m / i)%P*(LL)(g[pos]-g[i-1]+P)%P;ans%=P;}printf("%lld\n",ans);  }  
}