bzoj3944 Sum

bzoj3944 Sum

​​ 题目描述

给定一个正整数

N(N\le2^{31}-1)

N(N≤231−1)

求

ans_1=\sum_{i=1}^n\phi(i),ans_2=\sum_{i=1}^n \mu(i)

ans1=∑i=1nϕ(i),ans2=∑i=1nμ(i)

输入输出格式

输入格式：

一共T+1行 第1行为数据组数T(T<=10) 第2~T+1行每行一个非负整数N，代表一组询问

输出格式：

一共T行，每行两个用空格分隔的数ans1,ans2

输入输出样例

输入样例#1： 复制

6 1 2 8 13 30 2333 输出样例#1： 复制

1 1 2 0 22 -2 58 -3 278 -3 1655470 2 mmp 最后一个点是inf 然后爆int了 求φ φ 的公式在这里 ​​ 求μ μ 同理 ∑i=1n∑d|nμ(nd)×1(d)=∑i=1nε(i) ∑ i = 1 n ∑ d | n μ ( n d ) × 1 ( d ) = ∑ i = 1 n ε ( i ) 枚举d ∑d=1n∑i=1ndμ(i)=∑i=1nε(i) ∑ d = 1 n ∑ i = 1 n d μ ( i ) = ∑ i = 1 n ε ( i ) 设Hi表示μ μ 的前缀 即∑d=1nH(nd)=1 ∑ d = 1 n H ( n d ) = 1

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}int T;const int N=2e6+10;const int M=100011;int prime[N],tot,n;bool not_prime[N];ll phi[N],s[N],s1[N],mu[N];bool visit[N];inline ll getp(ll x){ if (x<=2e6) return phi[x];else return s[n/x];}inline ll getm(ll x){ if (x<=2e6) return mu[x];else return s1[n/x];}inline void calc(int x){ if (x<=2e6) return;if(visit[n/x]) return; visit[n/x]=1;ll tmp=(ll)x*x+x>>1,tmp1=1;unsigned int last; for (unsigned int i=2;i<=x;i=last+1){ last=x/(x/i);calc(x/i); tmp-=getp(x/i)*(last-i+1); tmp1-=getm(x/i)*(last-i+1); }s[n/x]=tmp;s1[n/x]=tmp1;}const int out_len=1<<16;char obuf[out_len],*oh=obuf;inline void write_char(char c){ if (oh==obuf+out_len) fwrite(obuf,1,out_len,stdout),oh=obuf; *oh++=c;}templateinline void W(T x){ static int buf[30],cnt; if (!x) write_char('0');else{ if (x<0) write_char('-'),x=-x; for (cnt=0;x;x/=10) buf[++cnt]=x%10+48; while(cnt) write_char(buf[cnt--]); }}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}int main(){ freopen("bzoj3944.in","r",stdin);// freopen("bzoj3944.out","w",stdout); T=read();phi[1]=mu[1]=1; for (int i=2;i<=2e6;++i){ if (!not_prime[i]) prime[++tot]=i,phi[i]=i-1,mu[i]=-1; for (int j=1;prime[j]*i<=2e6;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0) {mu[prime[j]*i]=0,phi[prime[j]*i]=phi[i]*prime[j];break;} else mu[prime[j]*i]=-mu[i],phi[prime[j]*i]=phi[i]*phi[prime[j]]; } }for (int i=2;i<=2e6;++i) phi[i]+=phi[i-1],mu[i]+=mu[i-1]; // for (int i=2;i<=2e6;++i) printf("%d\n",mu[i]); while(T--){ memset(visit,0,sizeof(visit)); n=read();if (n<=2e6) W(phi[n]),write_char(' '),W(mu[n]),write_char('\n'); else calc(n),W(s[1]),write_char(' '),W(s1[1]),write_char('\n'); //printf("%lld %lld\n",s[1],s1[1]); //printf("%lld %lld\n",calcphi(n),calcmu(n)); }flush(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。