首页 > 代码库 > bzoj4916 神犇和蒟蒻
bzoj4916 神犇和蒟蒻
Description
很久很久以前，有一只神犇叫yzy;
很久很久之后，有一只蒟蒻叫lty;
Input
请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;
Output
请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)};
请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)};
Sample Input
1
Sample Output
1
1
1
正解：杜教筛。
第一问答案是$1$。
第二问，先给个结论：$\varphi (n^{2})=n\varphi (n)$，于是我们要求$F(n)=\sum_{i=1}^{n}i\varphi (i)$。
设$f(n)=n\varphi (n)$，考虑$f$与$id$函数的狄利克雷卷积，$id*f(n)=\sum_{d|n}id(d)f(\frac{n}{d})$
$id*f(n)=n\sum_{d|n}\varphi (\frac{n}{d})=n^{2}$，那么$\sum_{i=1}^{n}id*f(i)=\frac{n(n+1)(2n+1)}{6}$
又$\sum_{i=1}^{n}id*f(i)=\sum_{i=1}^{n}\sum_{d|n}id(d)f(\frac{n}{d})=\sum_{ij\leq n}id(i)f(j)=\sum_{i=1}^{n}id(i)F(\left \lfloor \frac{n}{i} \right \rfloor)$
于是$F(n)=id(1)F(n)=\sum_{i=1}^{n}id*f(i)-\sum_{i=2}^{n}id(i)F(\left \lfloor \frac{n}{i} \right \rfloor)=\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^{n}id(i)F(\left \lfloor \frac{n}{i} \right \rfloor)$
然后直接用杜教筛的套路：数论分块+记忆化搜索就行了。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define rhl (1000000007)14 #define N (3000010)15 #define inf (1<<30)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 int vis[N],phi[N],prime[N],n,maxn,cnt;24 ll f[N],In2,In6;25 26 map <ll,ll> F,vi;27 28 il int gi(){29 RG int x=0,q=1; RG char ch=getchar();30 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();31 if (ch==‘-‘) q=-1,ch=getchar();32 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();33 return q*x;34 }35 36 il ll qpow(RG ll a,RG ll b){37 RG ll ans=1;38 while (b){39 if (b&1) ans=ans*a%rhl;40 a=a*a%rhl,b>>=1;41 }42 return ans;43 }44 45 il void sieve(){46 phi[1]=f[1]=1;47 for (RG int i=2;i<=maxn;++i){48 if (!vis[i]) prime[++cnt]=i,phi[i]=i-1;49 for (RG int j=1,k;j<=cnt;++j){50 k=i*prime[j]; if (k>maxn) break; vis[k]=1;51 if (i%prime[j]) phi[k]=phi[i]*phi[prime[j]];52 else{ phi[k]=phi[i]*prime[j]; break; }53 }54 }55 for (RG int i=2;i<=maxn;++i) f[i]=(f[i-1]+(ll)i*(ll)phi[i])%rhl; return;56 }57 58 il ll du(RG ll n){59 if (n<=maxn) return f[n]; if (vi[n]) return F[n];60 RG ll ans=n*(n+1)%rhl*(2*n+1)%rhl*In6%rhl,pos; vi[n]=1;61 for (RG ll i=2;i<=n;i=pos+1){62 pos=n/(n/i);63 ans-=(i+pos)*(pos-i+1)%rhl*du(n/i)%rhl*In2%rhl;64 if (ans<0) ans+=rhl;65 }66 return F[n]=ans;67 }68 69 il void work(){70 n=gi(),puts("1"),maxn=min(3000000,n),sieve();71 In2=qpow(2,rhl-2),In6=qpow(6,rhl-2);72 printf("%lld\n",du(n)); return;73 }74 75 int main(){76 File("phi");77 work();78 return 0;79 }
bzoj4916 神犇和蒟蒻
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。