题目传送门：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1239
传说中的杜教筛！虽然网上式子很多了，但还是推一推吧！
总体思路：
\(\left\{ {\begin{array}{*{20}{l}}
{f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\
{(\varphi \times I)(x) = id}\\
{g(n) = \sum\limits_{i = 1}^n {id(i)} }
\end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})} \)
至于杜教筛的顺逆推问题，感觉只能凑
不过想一想，能凑的也不过mu，phi这些
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MOD = 1000000007;
const int REV = 500000004;
const int MX = 5000000;
const int N = MX + 9;
unordered_map<LL,int> M;
int phi[N],pri[N],tot;
bool vis[N];
inline LL read(){
char c=getchar(); LL ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret;
}
inline void prework(){
phi[1] = 1;
for (int i=2;i<=MX;i++) {
if (!vis[i]) pri[++tot] = i, phi[i] = i - 1;
for (int j=1;j<=tot && pri[j]*i<=MX;j++) {
vis[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<=MX;i++) phi[i] += phi[i-1], phi[i] %= MOD;
}
int solve(LL w) {
if (w <= MX) return phi[w];
else if (M[w]) return M[w];
else {
int ret = ((w%MOD)*((w+1)%MOD)%MOD)*REV%MOD;
for (LL i=2,tmp;i<=w;i=tmp+1) {
tmp = w / (w/i); ret %= MOD;
ret -= (LL)solve(w/tmp)*(tmp-i+1) % MOD;
} ((ret%=MOD)+=MOD)%=MOD; M[w] = ret; return ret;
}
}
int main(){
prework();
printf("%d\n",solve(read()));
return 0;
}
哇塞，居然是沙发？留个名
Hi there to every body, it’s my first pay a quick
visit of this webpage; this webpage contains amazing and truly fine data in support of visitors.
Heya i am for the first time here. I came
across this board and I find It truly useful & it helped me out much.
I hope to give something back and help others like you aided
me.
I simply couldn’t leave your website prior to suggesting that I
really loved the usual information a person supply in your
guests? Is gonna be back often in order to check out new posts
I was suggested this web site via my cousin. I am now not certain whether or not this post
is written through him as no one else recognize
such unique approximately my problem. You’re amazing!
Thank you!
I do consider all of the concepts you’ve presented in your post.
They’re very convincing and will certainly work.
Nonetheless, the posts are too quick for starters.
May just you please prolong them a little from next time?
Thanks for the post.
This paragraph is actually a fastidious one it assists new the web people,
who are wishing in favor of blogging.
Excellent blog you have got here.. It’s hard to find excellent writing like yours nowadays.
I truly appreciate individuals like you! Take care!!
Awesome! Its really awesome paragraph, I have got much clear idea concerning
from this paragraph.
whoah this weblog is great i really like studying your articles.
Keep up the great work! You know, lots of individuals are
looking round for this info, you could aid them greatly.
Hello! This is my first visit to your blog! We are a group of volunteers and
starting a new initiative in a community in the same niche.
Your blog provided us beneficial information to work on. You have done a wonderful job!
When someone writes an paragraph he/she maintains the idea of a user in his/her brain that how a
user can know it. Therefore that’s why this paragraph is outstdanding.
Thanks!
Great beat ! I would like to apprentice while you amend your site, how can i subscribe
for a blog website? The account aided me a acceptable deal.
I had been tiny bit acquainted of this your broadcast offered bright clear idea
Fantastic beat ! I would like to apprentice whilst you amend your site,
how could i subscribe for a blog website? The account helped me a applicable deal.
I had been tiny bit acquainted of this your broadcast
provided brilliant clear concept
What’s up to all, how is all, I think every one
is getting more from this web page, and your views are fastidious in support of
new people.
It’s really a nice and useful piece of information. I’m glad that you shared this helpful information with us. Please keep us informed like this. Thank you for sharing.
Wonderful blog! I found it while searching on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Many thanks
This site was… how do you say it? Relevant!!
Finally I have found something which helped me. Thanks a lot!
I have learn a few good stuff here. Definitely value bookmarking for revisiting.
I wonder how much effort you set to create this kind of wonderful informative site.
Hey I know this is off topic but I was wondering if you knew of any widgets I could
add to my blog that automatically tweet my newest
twitter updates. I’ve been looking for a plug-in like this
for quite some time and was hoping maybe you would have some experience with something like
this. Please let me know if you run into anything. I truly
enjoy reading your blog and I look forward to your new
updates.
What a stuff of un-ambiguity and preserveness of precious experience regarding unexpected emotions.
Hi! This is kind of off topic but I need some advice from an established blog. Is it difficult to set up your own blog? I’m not very techincal but I can figure things out pretty quick. I’m thinking about making my own but I’m not sure where to start. Do you have any tips or suggestions? Many thanks