题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3944
好像没有什么特别的
但讲道理,下面是map,上面是unordered_map
讲道理啊!这™复杂度都不一样啊!
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000000+9; const int MX = 5000000; int mu[N],cnt,pri[N]; bool vis[N]; LL phi[N]; map<int,int> MU; map<int,LL> PHI; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void prework(){ mu[1] = phi[1] = 1; for (int i=2;i<=MX;i++) { if (!vis[i]) pri[++cnt] = i, mu[i] = -1, phi[i] = i-1; for (int j=1,w;j<=cnt && pri[j]*i<=MX;j++) { vis[i*pri[j]] = 1; w = pri[j]*i; if (i%pri[j]) mu[w] = -mu[i], phi[w] = phi[i]*(pri[j]-1); else {phi[w] = phi[i]*pri[j]; break;} } } for (int i=1;i<=MX;i++) mu[i] += mu[i-1], phi[i] += phi[i-1]; } inline int solve_mu(int w) { if (w <= MX) return mu[w]; else if (MU[w]) return MU[w]; else { int ret = 1; for (LL i=2,tmp;i<=w;i=tmp+1) { tmp = w / (w / i); ret -= solve_mu(w/tmp)*(tmp-i+1); } MU[w] = ret; return ret; } } int LL solve_phi(int w) { if (w <= MX) return phi[w]; else if (PHI[w]) return PHI[w]; else { LL ret = w * ((LL)w+1) / 2; for (LL i=2,tmp;i<=w;i=tmp+1) { tmp = w / (w/i); ret -= solve_phi(w/tmp)*(tmp-i+1); } PHI[w] = ret; return ret; } } int main(){ prework(); for (int t=read(),w;t;t--) w = read(), printf("%lld %d\n",solve_phi(w),solve_mu(w)); return 0; }
834930 286304This really is a proper weblog for would like to discover out about this subject. You realize a lot its almost challenging to argue along (not that I personally would wantHaHa). You in fact put the latest spin with a subject thats been discussed for a long time. Amazing stuff, just great! 879992
294132 180296Very intriguing information !Perfect just what I was looking for! 495856
334018 363245Speedily and easily build your internet traffic and PR, which provides Internet site visitors to add your page to any social bookmarking internet site. 621569
498472 126188Wonderful beat ! I wish to apprentice although you amend your internet site, how can i subscribe for a blog website? The account aided me a appropriate deal. I had been a little bit acquainted of this your broadcast provided bright clear concept 329617
930965 900852There is noticeably a bundle to learn about this. I assume you made specific good points in capabilities also. 224250
363204 291755Id need to talk to you here. Which is not some thing Which i do! I like reading an write-up that can make men and women believe. Also, thank you for permitting me to comment! 362421
369699 276772I extremely happy to discover this website on bing, just what I was looking for : D too bookmarked . 607924
622012 858632I enjoy your writing style truly enjoying this web web site . 923461
983155 596461I truly appreciated this gorgeous weblog. Make sure you keep up the great function. Finest Regards . 304877
243996 134133Hey! Excellent stuff, please keep us posted when you post something like that! 664404
505698 168539The when I just read a blog, Im hoping that this doesnt disappoint me approximately this one. Get real, Yes, it was my method to read, but When i thought youd have something intriguing to state. All I hear is really a number of whining about something which you could fix should you werent too busy trying to discover attention. 481095
420207 291191I got what you intend, saved to favorites , very decent internet internet site . 573627
886671 849488Read More HERE. I bookmarked it. 980499
19746 534457I like this internet website because so significantly utile stuff on here : D. 807596
I haven?¦t checked in here for some time as I thought it was getting boring, but the last few posts are good quality so I guess I will add you back to my everyday bloglist. You deserve it my friend 🙂
Real clean website , thanks for this post.