题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3025
数据加强版：http://oi.cdshishi.net/contestoi/problem_show.php?pid=1063
数据生成器（要求支持假分数）：http://paste.ubuntu.com/23391949/
好久没有做推式子的题目啦！
首先这题可以用Farey sequence直接做：https://en.wikipedia.org/wiki/Farey_sequence
具体实现上可能需要用Stern–Brocot tree：https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
上述做法把此题变成裸题，然而不知道上面的东西怎么办？
下面说一说使用莫比乌斯函数的O(nlog(n^2))的做法
注：以下讨论均针对于数据加强版，BZOJ上的原题可能不需要这么复杂
最外层先搞一个二分，假设二分到某一个值使得小于等于他的分数刚好有k个
那么我们只需要枚举分母，找到其中最大的一个输出即可
另外，这里的二分只能定分母、二分分子。不能够直接二分小数，原因待会儿说。
考虑到精度问题，我们定分母EPS=1e10（实际上也只能定为1e10，因为小了精度不够，大了要炸long long）
假设二分的分子为k，则现在我们需要求解的便是：\(\sum\limits_{y = 1}^n {\sum\limits_{x = 1}^{\left\lfloor {\frac{{yk}}{{EPS}}} \right\rfloor } {\sum\limits_{d|x,y} {\mu (d)} } } \)
稍微变形一下可以得到：\(\sum\limits_{d = 1}^n {\mu (d)\sum\limits_{y = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {\sum\limits_{x = 1}^{\left\lfloor {\frac{{\left\lfloor {\frac{{y \cdot d \cdot k}}{{EPS}}} \right\rfloor }}{d}} \right\rfloor } 1 } } \)
注意到x的上限有两个取整函数，因为取整函数有这个性质：\(\left\lfloor {\frac{{\left\lfloor {\frac{{\rm{y}}}{a}} \right\rfloor }}{b}} \right\rfloor = \left\lfloor {\frac{y}{{ab}}} \right\rfloor\)
所以才可以去掉上面的那个取整函数，这也是为什么不能直接二分实数，因为实数去不掉那个取整函数
我们继续推导，再次化简以后可以得到：\(\sum\limits_{d = 1}^n {\mu (d)\sum\limits_{y = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {\sum\limits_{x = 1}^{\left\lfloor {\frac{{yk}}{{EPS}}} \right\rfloor } 1 } } \)
这样的话，就可以线性处理后两个Σ，然后O(n)枚举d来计算了
另外还有一个小细节：x不仅受到分数值的限制，还受到n的限制，所以那里还需要特判一下
这题还有一种类似的做法，但可避免炸long long的风险：
考虑仪仗队那个题，因为方队左右对称，于是总可以把问题划归到方阵的右下部分
然后二分右下部分的斜率（定分母为n，二分分子）
二分到分子差只有1的时候，就暴力取出那个区间的所有分数，排序输出
这题我写的代码是第一种方式的，精度巨坑，必须是1e10，且不能有任何实数运算
#include<bits/stdc++.h>
#define LL long long
#define LD long double
using namespace std;
const int N = 100000+9;
const LL EPS = 1e10;
int pri[N],tot,n,cnt,mu[N];
LL f[N],K,vx,vy;
bool vis[N];
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 Get_Mu() {
mu[1] = 1;
for (int i=2;i<=n;i++) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot&&i*pri[j]<=n;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
}
}
inline LL Get(LL w) {
for (int i=1;i<=n;i++) f[i] = i * w / EPS;
for (int i=2;i<=n;i++) f[i] += f[i-1];
LL ret = 0, sta;
for (int i=1;i<=n;i++) {
sta = (LL)EPS * n / (w * i);
ret += f[min(n/(LL)i, sta)] * mu[i];
if (sta < n/i) ret += (n/i) * (n/i - sta) * mu[i];
}
return ret;
}
inline void Get_Ans(LL w) {
for (int y=1,x;y<=n;y++) {
x = min((LL)n, w * y / EPS);
if (x && (vx * y < vy * x || !vx))
vx = x, vy = y;
}
printf("%lld %lld\n", vx, vy);
}
int main(){
cin>>n>>K;
Get_Mu();
LL l=1, r=(LL)n*EPS, mid, ret;
while (l <= r) {
mid = l + r >> 1;
if (Get(mid) <= K) ret = mid, l = mid + 1;
else r = mid - 1;
}
Get_Ans(ret);
return 0;
}
For hottest news you have to go to see world-wide-web and on world-wide-web
I found this web site as a best web page for most up-to-date updates.
I loved as much as you will receive carried out
right here. The sketch is tasteful, your authored material stylish.
nonetheless, you command get bought an impatience over that you wish be delivering the following.
unwell unquestionably come further formerly again as exactly
the same nearly a lot often inside case you shield this increase.
Having read this I thought it was very enlightening. I appreciate you spending
some time and effort to put this content together.
I once again find myself spending a lot of
time both reading and posting comments. But so what, it was still worthwhile!
I pay a visit daily a few sites and information sites to read articles,
however this blog provides quality based posts.
You can certainly see your expertise in the work you write.
The world hopes for more passionate writers like you who are
not afraid to say how they believe. At all times go after your heart.
It’s enormous that you are getting ideas from this post as well as from our dialogue made here.
It is the best time to make a few plans for the future and it’s time to be
happy. I have read this submit and if I could I wish to
counsel you some fascinating things or suggestions.
Maybe you can write next articles relating to this article.
I want to learn even more issues about it!
Great items from you, man. I have take note your
stuff prior to and you’re simply extremely great.
I actually like what you’ve got here, certainly like
what you are saying and the way in which wherein you are saying it.
You are making it enjoyable and you still take care of to stay it smart.
I can’t wait to read much more from you. This is really a great web site.
Its like you read my mind! You seem to know a lot about this,
like you wrote the book in it or something. I think that you could do with some pics to drive the message home a bit, but instead of that,
this is great blog. An excellent read. I’ll
definitely be back.
Hi, i think that i saw you visited my web site thus i got here to return the want?.I am attempting to in finding issues to improve my site!I assume its ok to use some of your ideas!!
Hello, after reading this amazing article i am also cheerful to share my know-how here with
friends.
Right away I am going to do my breakfast, afterward having my breakfast coming
yet again to read additional news.
I always emailed this blog post page to all my friends, since if like to read it afterward my
friends will too.
Pretty nice post. I just stumbled upon your blog and wished to say that I have truly enjoyed browsing
your blog posts. After all I will be subscribing to your feed and I hope you
write again very soon!
hello there and thank you for your information – I have certainly picked up anything new from right here. I did however expertise a few technical issues using this website, since I experienced to reload the site a lot of times previous to I could get it to load correctly. I had been wondering if your web host is OK? Not that I’m complaining, but slow loading instances times will sometimes 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 could look out for a lot more of your respective interesting content. Make sure you update this again very soon..
What’s up to all, how is the whole thing, I think every
one is getting more from this web page, and
your views are good in favor of new users.
No matter if some one searches for his necessary thing, thus he/she desires to be available that in detail, thus that
thing is maintained over here.
Hi to all, how is all, I think every one is getting
more from this site, and your views are good in favor of new users.
This is really attention-grabbing, You’re a very skilled blogger.
I’ve joined your feed and look ahead to in search of more
of your wonderful post. Also, I have shared your web site in my social networks
Hi, I do believe this is an excellent blog. I stumbledupon it 😉
I’m going to return yet again since i have bookmarked it.
Money and freedom is the best way to change, may you
be rich and continue to help others.
Definitely believe that which you stated.
Your favorite justification appeared to be on the web the easiest
factor to consider of. I say to you, I definitely get irked
whilst folks think about worries that they just do not recognize about.
You controlled to hit the nail upon the top and defined out the whole thing without having side effect , other people can take
a signal. Will probably be back to get more.
Thank you
I am not sure where you’re getting your information, but
good topic. I needs to spend some time learning more or
understanding more. Thanks for fantastic info I was
looking for this info for my mission.
At this time I am ready to do my breakfast, after having my breakfast
coming over again to read further news.
Hmm it seems like your blog ate my first comment (it was extremely long) so
I guess I’ll just sum it up what I wrote and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog blogger but I’m still new to everything.
Do you have any tips for first-time blog writers?
I’d certainly appreciate it.
Thanks in support of sharing such a pleasant thought, post is fastidious, thats why i have read it completely
I think this is one of the most significant info for me.
And i’m glad reading your article. But wanna remark on few general
things, The website style is great, the articles is really nice : D.
Good job, cheers
Great article. I will be facing many of these issues as well..
Some really fantastic information, Sword lily I detected this. “Love consists in this, that two solitudes protect and touch and greet each other.” by Rainer Maria Rilke.