题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2818
离线版题目：http://paste.ubuntu.com/20184097/
这个题目，很容易想到枚举素数，然后求gcd=1的对数
用莫比乌斯函数+分段来搞的话，好像很常规，时间复杂度O(ln(n)*sqrt(n)+n)
然后就是看到这篇博客，发现可以直接用phi函数搞QAQ，时间复杂度O(ln(n)+n)
因为phi前缀和那里必须用long long搞得实际运行时间比莫比乌斯函数还要慢QAQ
莫比乌斯函数版本：
#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;
const int MAXN = 10000000+9;
int pri[MAXN],tot,mu[MAXN],n;
bitset<MAXN> tag;
inline void Get_mu(){
mu[1] = 1;
for (int i=2;i<=n;i++){
if (!tag[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot && pri[j]*i <= n;j++){
tag[i*pri[j]] = 1;
if (i % pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
}
for (int i=1;i<=n;i++) mu[i] += mu[i-1];
}
int main(){
scanf("%d",&n); Get_mu(); LL vout = 0;
for (int j=1;j<=tot && pri[j] <= n;j++) {
int k = pri[j], a=n/k;
for (int i=1,tmp;i<=a;i=tmp+1)
tmp = a/(a/i),
vout += (LL)(mu[tmp]-mu[i-1])*(a/i)*(a/i);
}
printf("%lld\n",vout);
return 0;
}
欧拉函数版本：
#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;
const int MAXN = 10000000+9;
int pri[MAXN],tot,n;
LL phi[MAXN],vout=0;
bitset<MAXN> tag;
inline void Get_Phi(){
phi[1] = 1;
for (int i=2;i<=n;i++){
if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
for (int j=1;j<=tot && pri[j]*i<=n;j++){
tag[pri[j]*i] = 1;
if (i % pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
else {phi[i*pri[j]] = phi[i]*pri[j]; break;}
}
}
for (int i=1;i<=n;i++) phi[i] += phi[i-1];
}
int main(){
scanf("%d",&n); Get_Phi();
for (int i=1;i<=tot && pri[i] <= n;i++)
vout += phi[n/pri[i]]*2 - 1;
printf("%lld\n",vout);
return 0;
}
I every time emailed this webpage post page to all my contacts, as if like to read it afterward my contacts will too.
Pretty! This was an incredibly wonderful post. Thanks for providing this info.
I like reading through a post that can make men and
women think. Also, thanks for permitting me to comment!
Hello, of course this paragraph is actually nice
and I have learned lot of things from it regarding blogging.
thanks.
This design is steller! You certainly know how to
keep a reader amused. Between your wit and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Great job. I really loved what you had to say, and more than that,
how you presented it. Too cool!
I just like the valuable information you provide for your articles.
I’ll bookmark your weblog and take a look at again right here frequently.
I’m quite certain I’ll be told a lot of new stuff right here!
Good luck for the next!
Hey very nice blog!
It’s going to be end of mine day, however before end I am reading this enormous article to improve my know-how.
What i do not realize is in reality how you’re not
actually much more neatly-preferred than you might be now.
You’re so intelligent. You already know thus considerably in relation to this matter, made me individually consider it from numerous various angles.
Its like men and women are not fascinated except it’s one thing to accomplish with Woman gaga!
Your individual stuffs great. All the time care for it up!
I love what you guys are up too. This kind of clever work and reporting!
Keep up the terrific works guys I’ve included you guys
to my own blogroll.
Wow, this piece of writing is fastidious, my sister is analyzing such things, therefore I am going to convey
her.
Nice blog here! Also your web site loads up fast! What web host are you using?
Can I get your affiliate link to your host? I wish my site loaded up as fast as yours lol
I don’t usually comment but I gotta state regards for the post on this special one : D.
Pretty nice post. I just stumbled upon your blog and wanted to say
that I have really enjoyed browsing your blog posts.
In any case I’ll be subscribing to your feed and I hope
you write again very soon!
Howdy! I could have sworn I’ve been to this site before but after checking
through some of the post I realized it’s new to me. Nonetheless, I’m definitely delighted I found it
and I’ll be bookmarking and checking back frequently!
These are really wonderful ideas in about blogging.
You have touched some fastidious factors here. Any way keep
up wrinting.
Hey there! I just wish to give you a huge thumbs up for your great information you have got here
on this post. I am coming back to your web site for more soon.
Hi, I think your site might be having browser compatibility issues.
When I look at your blog site in Chrome, it looks fine but
when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up!
Other then that, terrific blog!
It’s hard to find knowledgeable people for this topic, however, you seem like you
know what you’re talking about! Thanks
Hi Dear, are you actually visiting this website regularly, if so
afterward you will absolutely obtain pleasant knowledge.
Hey very nice web site!! Man .. Beautiful ..
Wonderful .. I will bookmark your blog and take the feeds additionally?
I’m satisfied to find so many helpful information right here
in the submit, we need develop extra techniques in this regard, thank you for sharing.
. . . . .
Hello, I enjoy reading all of your post. I wanted to write a little comment to support you.
I like the efforts you have put in this, regards for all the great posts.
wow, awesome post.Really looking forward to read more. Keep writing.