P8058题解

Miracle_1024 · 2023-05-24 06:56:36 · 题解

思路：

把所有分子和分母都小于 N 的最简真分数从小到大排成一行，形成的序列称为 Farey 序列。例如： N = 4 时序列是 \frac{1}{4} , \frac{1}{3} , \frac{1}{2} , \frac{2}{3} , \frac{3}{4}。求出 N 所对应的 Farey 序列中第 k 大的数。

首先我们二分答案 x，这样就转化为求 y = (n \text{ 的 Farey 序列中小于等于 } x \text{ 的数的个数}) 。

我们可以推出 y=\displaystyle\sum_{d=1}^n\mu(d)\times\displaystyle\sum_{i=1}^{[n/d]}[x\times i]。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100200;
int f[N],p[N],mu[N],n,k,s[N],t[N],tot;

void getprime(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!f[i]) p[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot;j++){
            if(i*p[j]>=N) break;
            f[i*p[j]]=true;
            if(i%p[j])
                mu[i*p[j]]=-mu[i];
            else{
                mu[i*p[j]]=0;
                break;
            }
        }
    }
}

int calc(double x){
    int ans=0;
    for(int i=1;i<=n;i++)
        t[i]=x*i;
    for(int i=1;i<=n;i++)
        if(mu[i])
            for(int j=1;j*i<=n;j++)
                ans+=mu[i]*t[j];
    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;
    }
}

int main(){
    scanf("%d%d",&n,&k);
    getprime();
    double l=0,r=1;
    while(r-l>1e-9){
        double mid=(l+r)/2;
        if(calc(mid)<k)l=mid;else r=mid;
    }
    int p,q;
    find(r,p,q);
    printf("%d %d\n",p,q);
    return 0;
}