【杜教筛】BZOJ4916[神犇(JZ)和蒟蒻(ZZK)]题解

xiaoxiao2021-02-28  8

题目概述

给出 n ,求 A=ni=1μ(i2),B=ni=1φ(i2)

解题报告

第一问…… i2 ?喜闻乐见输出 1

第二问,由于 φ(i2)=iφ(i) ,所以要求 ni=1iφ(i) (积性函数前缀和),那么我们就想到用杜教筛。xjb乱凑之后发现如果卷了 Id ,就可以得到:

S(n)=i=1ni2i=2niS(ni)=n(n+1)(2n+1)6i=2niS(ni) 然后就好了~

示例程序

#include<cstdio> #include<map> using namespace std; typedef long long LL; const int maxn=1000000,MOD=1e9+7,INV2=(MOD+1)/2,INV6=(MOD+1)/6; int n,p[maxn+5],pre[maxn+5]; bool pri[maxn+5];map<int,int> f; inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline void Make(){ pri[0]=pri[1]=true;pre[1]=1; for (int i=2;i<=maxn;i++){ if (!pri[i]) p[++p[0]]=i,pre[i]=(LL)(i-1)*i%MOD; for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxn;j++) if (i%p[j]) pre[t]=(LL)pre[i]*pre[p[j]]%MOD,pri[t]=true; else {pre[t]=(LL)pre[i]*p[j]%MOD*p[j]%MOD;pri[t]=true;break;} } for (int i=2;i<=maxn;i++) AMOD(pre[i],pre[i-1]); } int Solve(int n){ if (n<=maxn) return pre[n];if (f.count(n)) return f[n]; int ans=(LL)n*(n+1)%MOD*(n*2+1)%MOD*INV6%MOD; for (int l=2,r;l<=n;l=r+1){ r=n/(n/l);int now=(LL)(l+r)*(r-l+1)%MOD*INV2%MOD; AMOD(ans,MOD-(LL)now*Solve(n/l)%MOD); } return f[n]=ans; } int main(){ scanf("%d",&n);puts("1");Make(); return printf("%d\n",Solve(n)),0; }
转载请注明原文地址: https://www.6miu.com/read-1400267.html

最新回复(0)