题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2005
前传传送门：http://oi.cyo.ng/?p=477
之前%JCVB的没有成功。
今天又来%，基本上有思路了，真的是_(:з」∠)_
引理：\(\varphi (n) = \sum\limits_{d|n} {\frac{n}{d} \cdot \mu (d)}\)
证明：\(\varphi (n) = \sum\limits_{i = 1}^n {[\gcd (i,n) = = 1] = \sum\limits_{i = 1}^n {\sum\limits_{d|i} {\sum\limits_{d|n} {\mu (d) = \sum\limits_{d|n} {\mu (d) \cdot \sum\limits_{i = 1}^n {[\gcd (i,n) = = i] = } } } } } } \sum\limits_{d|n} {\mu (d) \cdot \frac{n}{d}}\)
我们之前的式子是：\(\sum\limits_{d = 1}^n {\sum\limits_{k = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {d \cdot \mu (k) \cdot \left\lfloor {\frac{n}{{d \cdot k}}} \right\rfloor } } \cdot \left\lfloor {\frac{m}{{d \cdot k}}} \right\rfloor\)
注意看好，我要变形啦！( •̀ ω •́ )y
不妨设：D=k*d,则有原式=\(\sum\limits_{D = 1}^n {\sum\limits_{d|D} {d \cdot \mu (\frac{D}{d}) \cdot } } \left\lfloor {\frac{n}{D}} \right\rfloor \cdot \left\lfloor {\frac{m}{D}} \right\rfloor \)
根据引理可以进一步简化为：\(\sum\limits_{D = 1}^n {\varphi ({\rm{D}})} \cdot \left\lfloor {\frac{n}{D}} \right\rfloor \cdot \left\lfloor {\frac{m}{D}} \right\rfloor \)
然后就可以线筛出欧拉函数后，\(\sqrt n \)分块就好，总时间复杂度：O(n)
#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;
const int MAXN = 100000+9;
int n,m,pri[MAXN],tot,tmp;
LL phi[MAXN],vout;
bitset<MAXN> tag;
inline void Get_Phi(){
phi[1] = 1;
for (int i=2;i<=m;i++){
if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
for (int j=1;j<=tot && pri[j]*i<=m;j++){
tag[i*pri[j]] = 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<=m;i++) phi[i] += phi[i-1];
}
int main(){
scanf("%d%d",&n,&m);
if (n > m) swap(n, m); Get_Phi();
for (int i=1;i<=n;i=tmp+1){
tmp = min(n/(n/i),m/(m/i));
vout += (LL)(phi[tmp]-phi[i-1])*(n/i)*(m/i);
}
printf("%lld\n",vout*2-(LL)n*m);
return 0;
}
哦，对了，这类直线上点的个数的问题，有一个神奇的结论：
（x,y）这个点到原点的连线上整点的个数为gcd(x,y)
为什么会有这个结论呢？
因为这个相当于把线段分成了完全相同的gcd(x,y)段
或者可以这样理解：
离原点最近的一个肯定是(x/gcd(x,y),y/gcd(x,y))
之后的每一整点都是他的整数倍，所以总共有gcd(x,y)个
—————————— UPD 2017.2.1 ——————————
今天又看了看这个玩意儿，为什么要$\sqrt n$分块QwQ
暴力不也这复杂度吗……
而且完全不知道$\sum\limits_{d|n} {\frac{n}{d} \cdot \mu (d)}$是$\varphi (n)$也完全可以做啊！
根据狄利克雷卷积，可以知道这货是积性函数，然后再推一推发现可以线筛，然后直接做就好啊！
—————————— UPD 2017.7.3 ——————————
我发现自己之前数学好强
现在看这个题已经不会了qwq
Hello there! This article couldn’t be written any better!
Looking through this article reminds me of my previous roommate!
He always kept preaching about this. I most certainly will forward this
information to him. Fairly certain he will have a very good read.
Thank you for sharing!
Pretty great post. I simply stumbled upon your weblog and wanted to say that
I have truly loved browsing your weblog posts. In any
case I’ll be subscribing in your feed and I am hoping you
write again very soon!
Today, I went to the beachfront with my kids. I found a sea shell and gave it
to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear. She never
wants to go back! LoL I know this is entirely off topic
but I had to tell someone!
My programmer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the expenses. But he’s tryiong none the less.
I’ve been using Movable-type on a variety of websites for about a year and
am concerned about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can transfer all my wordpress posts into it?
Any kind of help would be really appreciated!
Today, I went to the beach with my kids. I found
a sea shell and gave it to my 4 year old daughter
and said “You can hear the ocean if you put this to your ear.” She
put the shell to her ear and screamed. There was a hermit crab inside and
it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell
someone!
Hey I am so thrilled I found your blog, I really found you
by error, while I was researching on Aol for something else, Anyhow I am here now and would just like to say
thanks a lot for a remarkable post and a all round exciting blog (I
also love the theme/design), I don’t have time to
read it all at the minute but I have bookmarked it and also added
in your RSS feeds, so when I have time I will be back
to read much more, Please do keep up the superb work.
Hi! This post couldn’t be written any better!
Reading this post reminds me of my old room mate!
He always kept talking about this. I will forward this post to him.
Pretty sure he will have a good read. Thank you for sharing!
That is a great tip especially to those fresh to the blogosphere.
Simple but very accurate info… Thanks for sharing this one.
A must read post!
Its like you read my mind! You seem to know so much about this, like you
wrote the book in it or something. I think that you could
do with a few pics to drive the message home a little bit, but other than that, this is magnificent blog.
A great read. I’ll certainly be back.
This is my first time go to see at here and i am genuinely impressed to read all at one place.
Hello! This post could not be written any better! Reading this
post reminds me of my previous room mate! He always kept chatting about this.
I will forward this article to him. Pretty sure he will have a good read.
Many thanks for sharing!
This is very interesting, You are a very skilled blogger.
I’ve joined your feed and look forward to seeking more of your
excellent post. Also, I have shared your website in my social networks!
I really love your site.. Excellent colors & theme.
Did you build this site yourself? Please reply back as
I’m trying to create my very own blog and want to find out where you got this from
or exactly what the theme is named. Thank you!
Hello just wanted to give you a quick heads up. The text in your article seem to be running off the screen in Chrome.
I’m not sure if this is a format issue or something to do
with web browser compatibility but I thought I’d
post to let you know. The design look great though! Hope you
get the issue resolved soon. Kudos
I don’t even know how I ended up here, however
I assumed this publish used to be good. I do not know who you’re however certainly you’re going to
a well-known blogger if you are not already. Cheers! pof natalielise
I appreciate, result in I found just what I was having a look for.
You’ve ended my 4 day long hunt! God Bless you man. Have
a nice day. Bye
I loved as much as you’ll receive carried out right here.
The sketch is attractive, your authored subject matter
stylish. nonetheless, you command get got an shakiness over that you wish
be delivering the following. unwell unquestionably come further
formerly again as exactly the same nearly very often inside case you shield this hike.
Hi to all, how is all, I think every one is getting more from this web site, and your views are fastidious designed for new people.
Do you mind if I quote a couple of your articles as long
as I provide credit and sources back to your blog? My blog
is in the very same niche as yours and my visitors would certainly benefit from some of the information you present here.
Please let me know if this alright with you. Thank you!
Howdy just wanted to give you a brief heads up
and let you know a few of the pictures aren’t loading properly.
I’m not sure why but I think its a linking issue.
I’ve tried it in two different browsers and both show the same results.
Hello, after reading this awesome article i am too happy to share my know-how here with colleagues.
plenty of fish natalielise
Hi there, I believe your web site could be having internet
browser compatibility problems. Whenever I look at your site in Safari, it looks fine however,
if opening in Internet Explorer, it’s got some overlapping issues.
I simply wanted to provide you with a quick heads up!
Other than that, excellent site!
I got this web site from my friend who informed me about this web page
and at the moment this time I am browsing this web page and reading very
informative articles at this time.
Write more, thats all I have to say. Literally, it seems as though you
relied on the video to make your point. You obviously know what youre talking about, why waste your
intelligence on just posting videos to your weblog when you
could be giving us something enlightening to read?
May I simply just say what a comfort to uncover somebody that really knows what they’re discussing
online. You certainly realize how to bring a problem to light and make it
important. More and more people ought to check this out and understand this
side of your story. I was surprised that you are not more popular since you definitely possess the gift.
It is in reality a great and useful piece of info. I’m glad that you shared this useful info with us.
Please keep us up to date like this. Thanks for sharing.
I am regular visitor, how are you everybody? This paragraph posted at
this web site is actually good.
Asking questions are in fact fastidious thing if
you are not understanding anything totally, however this paragraph offers fastidious understanding yet.
Your style is really unique in comparison to other people I’ve read stuff
from. Thank you for posting when you have the opportunity, Guess I will just book mark this site.
I’m really loving the theme/design of your web site. Do you ever run into
any web browser compatibility issues? A number of my blog readers have complained about my site not working correctly in Explorer
but looks great in Firefox. Do you have any suggestions to help fix this issue?
What’s up to every body, it’s my first pay a quick visit of
this website; this webpage carries amazing and actually good information designed
for readers.
What a stuff of un-ambiguity and preserveness of precious knowledge regarding unpredicted emotions.
Please let me know if you’re looking for a article author
for your site. You have some really great articles and
I feel I would be a good asset. If you ever want to take some
of the load off, I’d absolutely love to write some material for your
blog in exchange for a link back to mine. Please send me an e-mail if interested.
Thanks!
I am in fact pleased to read this blog posts which carries lots of helpful information, thanks for
providing such statistics.
My brother suggested I would possibly like this web site.
He was once totally right. This put up actually made my day.
You cann’t consider simply how much time I had spent for this info!
Thank you!
Every weekend i used to go to see this web site, for the reason that i
wish for enjoyment, for the reason that this this site conations actually nice funny stuff too.
Great post.
Why viewers still make use of to read news papers
when in this technological globe all is existing on net?
Hi colleagues, its great article on the topic of tutoringand fully defined, keep it
up all the time.
Ahaa, its fastidious dialogue on the topic of this paragraph here at this webpage, I have read all that, so at
this time me also commenting at this place.
Pretty! This was a really wonderful article. Many thanks for supplying this
info.
Write more, thats all I have to say. Literally, it seems as
though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just posting videos to your site when you could be giving
us something enlightening to read?
Howdy! I know this is kind of off-topic however I had to ask.
Does running a well-established blog such as yours require a massive amount work?
I’m brand new to writing a blog but I do write in my
diary every day. I’d like to start a blog so I will be able
to share my experience and feelings online.
Please let me know if you have any ideas or tips for new aspiring blog owners.
Appreciate it!
After looking into a handful of the blog posts on your web site, I really appreciate your technique of blogging.
I bookmarked it to my bookmark webpage list and will be checking back in the near future.
Please check out my web site too and tell me what you think.
This information is priceless. When can I find out more?
What’s up, I want to subscribe for this web site to obtain latest updates, thus where can i do
it please help.
This is the perfect web site for anybody who really wants to find out about this topic.
You realize a whole lot its almost tough to argue with you (not that I actually would want to…HaHa).
You definitely put a brand new spin on a subject that’s been discussed for ages.
Great stuff, just wonderful!
It’s amazing to pay a quick visit this web page and reading the views of all
friends about this piece of writing, while I am also keen of getting experience.
I am really loving the theme/design of your web site. Do
you ever run into any web browser compatibility issues? A handful of my blog visitors have
complained about my blog not working correctly in Explorer but looks great in Firefox.
Do you have any recommendations to help fix this problem?
I’m really impressed with your writing skills
as well as with the layout on your weblog.
Is this a paid theme or did you modify it
yourself? Either way keep up the nice quality writing,
it is rare to see a nice blog like this one today.
I do not even know how I ended up here, but I thought this
post was good. I don’t know who you are but definitely you
are going to a famous blogger if you aren’t already 😉 Cheers!
Hello there, I discovered your blog by means of Google while searching
for a related topic, your web site got here up, it
looks good. I’ve bookmarked it in my google bookmarks.
Hello there, simply turned into aware of your blog thru Google, and found that it is really informative.
I am going to watch out for brussels. I’ll be
grateful should you continue this in future. A lot of folks can be benefited from your writing.
Cheers!
Hello, its fastidious piece of writing about media print, we all understand media is a great source
of information.
Excellent weblog here! Additionally your site quite a bit up fast!
What web host are you the usage of? Can I am getting your affiliate hyperlink to
your host? I desire my website loaded up as quickly as yours lol
At this time it sounds like Movable Type
is the best blogging platform available right now.
(from what I’ve read) Is that what you are using on your blog?
I’m really loving the theme/design of your site. Do you ever
run into any internet browser compatibility issues?
A handful of my blog visitors have complained about my
site not operating correctly in Explorer but looks great in Firefox.
Do you have any recommendations to help fix this issue?
Hi there everyone, it’s my first pay a quick visit at this website,
and paragraph is genuinely fruitful designed
for me, keep up posting these types of articles or reviews.
Hi there! Do you know if they make any plugins to help with Search Engine Optimization? I’m
trying to get my blog to rank for some targeted
keywords but I’m not seeing very good success.
If you know of any please share. Thanks!
I’m not sure why but this blog is loading very slow for me.
Is anyone else having this issue or is it a issue on my
end? I’ll check back later on and see if the problem still exists.
I’ve been exploring for a little for any high-quality articles or weblog
posts on this kind of space . Exploring in Yahoo I at
last stumbled upon this site. Studying this info So i’m satisfied
to exhibit that I have an incredibly excellent
uncanny feeling I found out exactly what I needed.
I such a lot without a doubt will make sure to do not fail to remember this
website and provides it a glance regularly.
naturally like your web-site but you have to test the spelling on quite a
few of your posts. A number of them are rife with spelling issues and I find
it very troublesome to tell the reality then again I will definitely come back again.
I do not even know the way I ended up right here, but I
thought this put up used to be great. I don’t
recognize who you might be but definitely you’re going to a famous blogger if you
are not already. Cheers!
I believe this is among the such a lot important info for me.
And i am happy studying your article. However wanna commentary on some basic things, The website taste is wonderful, the articles is
really nice : D. Just right job, cheers
Hi there, I discovered your blog by way of Google while searching for
a similar subject, your site got here up, it
appears to be like great. I have bookmarked it in my google bookmarks.
Hello there, just was aware of your weblog through Google, and found that it’s really informative.
I’m gonna be careful for brussels. I will be grateful in the event you proceed
this in future. Lots of folks will likely be benefited out of your writing.
Cheers!
Hi there, just became aware of your blog through Google, and found that it’s really informative.
I am gonna watch out for brussels. I will appreciate if you continue this in future.
Numerous people will be benefited from your writing. Cheers!
Hi, i believe that i saw you visited my blog so i got here
to go back the desire?.I am attempting to find issues to improve my web site!I suppose its adequate to use some of your
ideas!!
Your means of describing the whole thing in this article is truly fastidious, every one can without difficulty
know it, Thanks a lot.
Howdy! This post could not be written any better!
Going through this article reminds me of my
previous roommate! He constantly kept talking about this.
I am going to forward this post to him. Fairly certain he’ll
have a good read. Many thanks for sharing!
Its good as your other blog posts : D, appreciate it for posting. “What makes something special is not just what you have to gain, but what you feel there is to lose.” by Andre Agassi.
Marvelous, what a weblog it is! This weblog gives helpful data
to us, keep it up.
The other day, while I was at work, my cousin stole my iphone
and tested to see if it can survive a 40 foot drop, just so she can be a youtube
sensation. My apple ipad is now broken and she has 83 views.
I know this is completely off topic but I had to share it with someone!
I loved as much as you’ll receive carried out right here.
The sketch is tasteful, your authored material stylish.
nonetheless, you command get got an nervousness over that you
wish be delivering the following. unwell unquestionably
come further formerly again since exactly the same nearly a lot often inside case you shield this
hike.
Spot on with this write-up, I really think this amazing site needs a great deal more attention. I’ll probably be returning to see more, thanks for the advice!
hello there and thank you for your information – I’ve definitely picked up anything new from right here.
I did however expertise a few technical points using this site, since I experienced to reload the site many times previous to I
could get it to load properly. I had been wondering if your hosting is OK?
Not that I am complaining, but slow loading instances times will
often affect your placement in google and can damage your high quality score
if ads and marketing with Adwords. Well I am adding this RSS to my email and can look out for a lot more of your respective intriguing content.
Ensure that you update this again soon.
I’m gone to tell my little brother, that he should also visit this blog on regular basis to take updated from most recent information.
Hello there! I could have sworn I’ve been to this website before but after reading through some of the post I realized it’s new to me.
Nonetheless, I’m definitely glad I found it and I’ll be bookmarking and checking back frequently!
We are a group of volunteers and starting a new scheme in our community.
Your web site offered us with valuable info to work on. You have done
an impressive job and our whole community will be thankful to you.
You ought to be a part of a contest for one of the most useful
blogs on the internet. I will recommend this
website!
Thanks for this post, I am a big fan of this site would like to keep updated.