hdu5628 : Clarke and math（线性筛）

本文主要是介绍hdu5628 : Clarke and math（线性筛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题以前用快速幂写的
今天用线性筛写了一下，真刺激
大概就是说那个东西是
$f*1^k$
然后你只要算出来$1^k$
就可以$O(nlogn)$卷积了
关于算$1^k$当然可以直接快速幂
$O(nlognlogk+nlogn)$
然而有更好的做法，我们可以线性筛
首先因为$1$是积性函数
所以$F=1^k$也是积性函数
所以我们只需要考虑$F(p^r)$的取值就好了
我们可以发现每个$p$都是一样的
所以就相当于在一个$k*(r+1)$的网格上走
从$(1,1)$到$(k,r+1)$的方案数为$C(k+r-1,r)$
然后就可以处理一下逆元直接筛了
代码：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return f==1?x:-x;
}
const int N=1e5+5,mod=1e9+7;
inline void inc(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int cnt,prime[N],vis[N],e[N];
int F[N],f[N],g[N],inv[N];
int main(){int T=read();for(int S=1;S<=T;++S){memset(e,0,sizeof e);memset(vis,0,sizeof vis);memset(g,0,sizeof g);int n=read(),k=read();F[1]=1;inv[0]=inv[1]=1;cnt=0;for(int i=2;i<=n;++i)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;for(int i=2;i<=n;++i){if(!vis[i]){prime[++cnt]=i;F[i]=k;e[i]=1;}for(int j=1;j<=cnt && i*prime[j]<=n;++j){vis[i*prime[j]]=1;if(i%prime[j]==0){F[i*prime[j]]=1LL*F[i]*inv[e[i]+1]%mod*(k+e[i])%mod;e[i*prime[j]]=e[i]+1;break;}else{F[i*prime[j]]=1LL*F[i]*F[prime[j]]%mod;e[i*prime[j]]=1;}}}for(int i=1;i<=n;++i)f[i]=read();for(int i=1;i*i<=n;++i){inc(g[i*i],1LL*f[i]*F[i]%mod);for(int j=i+1;i*j<=n;++j){inc(g[i*j],1LL*f[i]*F[j]%mod);inc(g[i*j],1LL*f[j]*F[i]%mod);}}for(int i=1;i<n;++i)printf("%d ",g[i]);printf("%d\n",g[n]);}return 0;
}

这篇关于hdu5628 : Clarke and math（线性筛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---