BZOJ 3739: DZY loves math VIII（莫比乌斯反演）
Posted On 2019年4月10日
3739: DZY loves math VIII
然后我就自闭了
然而题解告诉窝：只有squre free的才有贡献，暴搜乱搞即可，O(乱搞)+O(nlogn)=O(能过)
|
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 50 51 52 53 54 55 56 |
#include <cstdio> #include <bitset> #include <iostream> #include <cstdlib> using namespace std; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e7+100,up=1e7,siz=maxn,N=10000000; int a[maxn]; int sum[maxn],prime[maxn],miu[maxn],vis[maxn],cnt; inline void pre() { int CNT=0; miu[1]=1; for (int i=2;i<=N;i++) { if (!vis[i])prime[++CNT]=i,miu[i]=-1,vis[i]=i; for (int j=1;1ll*prime[j]*i<=N&&j<=CNT;j++) { vis[i*prime[j]]=prime[j]; if (i%prime[j]==0)break; miu[prime[j]*i]=-miu[i]; } } } int f[maxn]; int dfs(const int k,const int x,const int v) { if (k>cnt) { f[x]+=v; return miu[x]*f[x]; } return dfs(k+1,x*a[k],v)+dfs(k+1,x,v); } signed main() { int T=read(); pre(); for (int i=1;i<=N;i++) { sum[i]+=sum[i-1]; if (miu[i]) { cnt=0; for (int x=i;x!=1;x/=vis[x])a[++cnt]=vis[x]; sum[i]+=miu[i]*dfs(1,1,miu[i]); } } for (int i=1;i<=T;i++)printf("%d\n",sum[read()]); } |
Subscribe
0 评论