「P8058 [BalkanOI2003] Farey 序列」
_Fontainebleau_
·
·
题解
题意
### 做法
~~为什么讨论区会有类欧？一定是我太逊了。~~
二分那个数，求当前 Farey 序列中比它小的个数。
具体地，设 $\operatorname{Rank}(x)$ 表示 $n$ 级 Farey 数列有几个小于 $x$，$f(i)$ 表示 $n$ 阶 Farey 数列中分母为 $i$，且小于 $x$ 的数量。
则显然 $\displaystyle\operatorname{Rank}(x)=\sum_{i=1}^nf(i),f(i)=\lfloor{ix}\rfloor-\sum_{d<i,d\mid{i}}f(d)$，$f(i)$ 可以 $O(n\log{n})$ 筛。
由于每次都要调用，最后就是 $O(n\log^2n)$。
改进：
注意到 $\operatorname{Rank(x)}$ 是 $\left\lfloor{ix}\right\rfloor,1\le{i}\le{n}$ 的线性组合。再回顾 $f(i)$ 的式子，这个系数是与 $x$ 无关的。这启示我们先预处理出 $\operatorname{Rank}(x)$ 中 $\left\lfloor{ix}\right\rfloor$ 的系数，不用每次重新算 $f$。
具体而言，令 $g(i)$ 表示 $\left\lfloor{ix}\right\rfloor$ 的系数。**$\left\lfloor{ix}\right\rfloor$ 第一次出现是在 $f(i)$ 中，此后，每一次一旦出现 $\left\lfloor{tx}\right\rfloor,t=ki,k\in\mathbb Z_{>1}$，$\left\lfloor{ix}\right\rfloor$ 的系数都一定增加 $\left\lfloor{tx}\right\rfloor$ 系数的相反数**，所以我们可以得到：$\displaystyle g(i)=1-\sum_{t>i,i\mid{t}}g(t)$。我们同样可以 $O(n\log{n})$ 先筛出来 $g$，然后每次可以 $O(n)$ 求 $\operatorname{Rank}(x)$。最后时间复杂度就是 $O(n\log{n})$。
最后再在 Farey 序列上找这个数即可。比较简单，不再赘述？
### 代码
```cpp
#include<bits/stdc++.h>
#define eps 1e-9
using namespace std;
int n,k,c[100005];
inline void S(int n)
{
for(int i=1;i<=n;i++) c[i]=1;
for(int i=n;i>=1;i--)
for(int t=i*2;t<=n;t+=i)
c[i]-=c[t];
}
inline int C(double x)
{
int ans=0;
for(int i=1;i<=n;i++) ans+=c[i]*int(x*i);
return ans;
}
void find(double x,int &p,int &q)
{
p=0,q=1;
for(int i=1;i<=n;i++)
{
int tmp=x*i;
if(abs(double(p)/double(q)-x)>abs(double(tmp)/double(i)-x))
p=tmp,q=i;
}
}
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
n=read(),k=read();
S(n);
double l=0,r=1;
while(r-l>eps)
{
double mid=(l+r)/2;
if(C(mid)<k) l=mid;
else r=mid;
}
int p,q;
find(r,p,q);
printf("%d %d\n",p,q);
return 0;
}
```