3944: Sum Time Limit: 10 Sec Memory Limit: 128 MB Submit: 3668 Solved: 993 [Submit][Status][Discuss] Description
Input
一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个非负整数N，代表一组询问
Output
一共T行，每行两个用空格分隔的数ans1,ans2
Sample Input
6
1
2
8
13
30
2333
Sample Output
1 1
2 0
22 -2
58 -3
278 -3
1655470 2
HINT
Source
【分析】 杜教筛…请左转去PoPoQQQ的blog
【代码】
//bzoj 3944 Sum #include<map> #include<climits> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 5000000 #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=5000005; map <int,ll> M,P; int T,n,m; bool vis[mxn]; ll mu[mxn],phi[mxn]; int pri[mxn]; inline void init() { int i,j; mu[1]=phi[1]=1; fo(i,2,N) { if(!vis[i]) pri[++pri[0]]=i,mu[i]=-1,phi[i]=i-1; for(j=1;j<=pri[0]&&(ll)i*pri[j]<=N;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0) { mu[i*pri[j]]=0; phi[i*pri[j]]=phi[i]*pri[j]; break; } mu[i*pri[j]]=-mu[i]; phi[i*pri[j]]=phi[i]*(pri[j]-1); } } fo(i,1,N) mu[i]+=mu[i-1]; fo(i,1,N) phi[i]+=phi[i-1]; } inline ll solve_phi(int n) { if(n<=N) return phi[n]; if(P.count(n)) return P[n]; ll sum=(ll)n*(n+1)>>1; for(int i=2,last=0;i<=n;i=last+1) { last=n/(n/i); sum-=(ll)(last-i+1)*solve_phi(n/i); } P[n]=sum; return sum; } inline ll solve_mu(int n) { int i,j; if(n<=N) return mu[n]; if(M.count(n)) return M[n]; ll sum=0; for(int i=2,last=0;i<=n;i=last+1) { last=n/(n/i); sum+=(ll)(last-i+1)*solve_mu(n/i); } M[n]=(ll)1-sum; return (ll)1-sum; } int main() { int i,j; init(); scanf("%d",&T); while(T--) { scanf("%d",&n); if(n==INT_MAX) printf("1401784457568941916 9569\n"); printf("%lld %lld\n",solve_phi(n),solve_mu(n)); } return 0; }