Enumerating Rational Numbers 题解

先下结论，这道题是一道欧拉函数板子题

观察题面可以发现，生成的分数有如下特性:

• 分数都是最简分数
• 分母与分子互质，且 分子 $ \le $ 分母
• 当然第一个除外，那个特判即可，不用纳入考虑范围

我们知道，对于任意正整数 n ，欧拉函数，即 \(\varphi(n)\) 是小于 n 的正整数中与 n 互质的数的数目；此处分母与分子的关系与此相同，所以容易联想到，可以通过欧拉函数求第 \(k\) 个分数，即 \(\varphi(p)\) 的值代表以 p 为分母的最简分数的个数。

接下来考虑如何求出第 \(k\) 个分数的值，既然以每个正整数为分母的最简分数个数已经求出，结合数据范围，此处考虑二分查找，查找到第一个合适的作为分母，之后枚举分子并求解即可。

细节：

• 根据样例可知，分母分子的最大值为 200000 ，所以数组仅需开到 200000
• 0/1 的情况需要特判，因为这没有算进欧拉函数值中，求前缀和时也要 +1
• gcd建议手写，变量建议全开 long long ，毕竟不开long long见祖宗。

具体做法：

1. 求出 1~200000 的欧拉函数值并求前缀和
2. 进行一个二分，求出分母
3. 循环枚举分子求解即可

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005; 
long long prime[maxn],cnt,n=200005,phi[maxn]={0,2},sumphi[maxn]={0,1};
bool vis[maxn];
void f(){//欧拉筛求解欧拉函数
    for(int i=2;i<=maxn-5;i++){
	    if(vis[i]==0) prime[++cnt] = i, phi[i] = i-1;
	    for(int j=1;j<=cnt;j++){
	    	int tmp = i*prime[j];
	    	if(tmp>n)break;
    		vis[tmp] = 1;
    		if(i%prime[j]==0) { 
    			phi[tmp] = phi[i]*prime[j];
	    		break;
	    	}
    		else phi[tmp] = phi[i]*(prime[j]-1);
    	}
    } 
    for(int i=1;i<=maxn-4;i++){
        sumphi[i]=sumphi[i-1]+phi[i];
    }
    return;
}
long long gcd(long long a,long long b){
    if(a+b==1)return 1;   
    if(b){
        while((a%=b) && (b%=a));
    }
    return a+b;
}
void solve(long long x){
    if(x==1){
        printf("0/1\n");
        return;
    }
    int l=lower_bound(sumphi+1,sumphi+200001,x)-sumphi;
    x-=sumphi[l-1];//x用于统计答案分数前分数的个数（包括答案分数本身）
    for(long long i=1;i<=l-1;i++){
        if(gcd(i,l)==1)x--;
        if(x==0){
            printf("%lld/%lld\n",i,l);
            return;
        }
    }
    return;
}
int main(){
    f();
    while(1){
        long long c;
        cin>>c;
        if(c==0)break;
        solve(c);
    }
    return 0;
}
//from chpyx2

Written by ChpyX2