【洛谷P5106】dkw的lcm
mrsrz
10月 19, 2019
数论
题目大意：
给定 $n,k$，求下面式子的值。
题解：
考虑 $\varphi$ 是积性函数，容易想到对不同的质数分别考虑。
考虑质数 $p$，当其贡献为 $\varphi(p^t)$ 时，$i_1,i_2,\dots,i_k$ 中至少有一个数要有 $p^t$ 因子，且不能有 $p^{t+1}$ 因子。
考虑 $f(i)$ 表示最大指数（上面的 $t$）为 $i$ 的方案数，$g(i)$ 表示最大指数小于等于 $i$ 的方案数。
显然有 $f(i)=g(i)-\sum_{j=1}^{i-1}f(j)$.
考虑求 $g(i)$。容易想到，$1\sim n$ 中包含 $p^t$ 因子的数的个数为 $\lfloor\frac{n}{p^t}\rfloor$，那么 $1\sim n$ 中不包含 $p^{t+1}$ 的数的个数为 $n-\lfloor\frac{n}{p^{t+1}}\rfloor$.
所以 $g(i)=(n-\lfloor\frac{n}{p^{i+1}}\rfloor)^k$.
然后这部分的贡献为 $\prod_{t} \varphi(p^t)^{f(t)}$.
由于 $f$ 求的是指数部分，根据欧拉定理，应对 $10^9+6$ 取模而不是 $10^9+7$。
对每个质因子计算贡献即可。
时间复杂度 $O(n\log n)$。
Code：
#include<iostream>
using namespace std;
const int N=1e6+5,md=1e9+7;
typedef long long LL;
int n,k,pri[N/10],tot,ans=1;
bool vis[N];
inline int pow(int a,int b,const int&md){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)
if(b&1)ret=(LL)ret*a%md;
return ret;
}
void sieve(int n){
for(int i=2;i<=n;++i){
if(!vis[i])pri[++tot]=i;
for(int j=1;j<=tot&&i*pri[j]<=n;++j){
vis[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
int main(){
cin>>n>>k;
sieve(n);
for(int i=1;i<=tot;++i){
const int p=pri[i];
int pre=pow(n-n/p,k,md-1);
for(int j=1,x=p;;x*=p,++j){
int f=(pow(n-n/((LL)x*p),k,md-1)-pre+md-1)%(md-1);
(pre+=f)%=md-1;
ans=((LL)ans*pow(x/p*(p-1),f,md))%md;
if(n/p<x)break;
}
}
cout<<ans<<endl;
return 0;
}