【bzoj4407】于神之怒加强版莫比乌斯反演+狄利克雷卷积

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

Description

给下N,M,K.求
这里写图片描述
Input

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

如题
Sample Input

1 2

3 3
Sample Output

HINT

1<=N,M,K<=5000000,1<=T<=2000

题解：
Orz YZH

JudgeOnline/upload/201603/4407.rar

这里写图片描述

第一次打狄利克雷卷积。两个积性函数的卷积F（D）是积性函数，可用线性筛求。
如果D是质数,F(D)=D^k-1
如果D不是质数,他会被他最小的质因子p筛到 F(D)=F(D/p)*p^k

代码

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=5000001;
int F[N],f[N],flag[N],k,tot,p[N],ans;
inline int gpow(int x,int y)
{int ans=1;while (y){if (y&1) ans=(ll)ans*x%mod;y>>=1;x=(ll)x*x%mod;}return ans;
}
void preparation()
{F[1]=1;for (int i=2;i<N;i++){if (!flag[i]){f[i]=gpow(i,k);F[i]=f[i]-1;p[++tot]=i;}for (int j=1;j<=tot&&i*p[j]<N;j++){flag[i*p[j]]=1;if (i%p[j])F[i*p[j]]=(ll)F[i]*F[p[j]]%mod;else{F[i*p[j]]=(ll)F[i]*f[p[j]]%mod;break;}}}for (int i=1;i<N;i++) (F[i]+=F[i-1])%=mod;
}
int main()
{int Case=read();k=read();preparation();while (Case--){int n=read(),m=read();if (n>m) swap(n,m);ans=0;for (int i=1,pos=0;i<=n;i=pos+1){pos=min(n/(n/i),m/(m/i));(ans+=1LL*(n/i)*(m/i)%mod*(F[pos]-F[i-1])%mod)%=mod;}printf("%d\n",(ans+mod)%mod);}return 0;
}