yukicoder : No.2262 Fractions

なるほど…。
https://yukicoder.me/problems/no/2262

問題

整数N,Kが与えられる。
分子分母がN以下の既約分数を昇順に並べたとき、K番目に来るものは何通りか。

1未満の既約分数がM個あるとき、加えて1/1が1つあり、その後、1未満の既約分数列を分子分母反転して順番の逆にしたものがもうM個続く。
よって、Kが(M+2)以上(2M+1)以下の場合は、(2M+2-K)番目の既約分数を求めて分子分母反転させればよい。

以降、1未満の既約分数のうちK番目のものを考える。
真の解がRであるとき、(m-1)/(N^2)＜R≦m/(N^2)を満たすRは、mごとに高々1個しかない。
そこで、mを二分探索すればよい。

分母Qに対し、分子がP以下かつQに互いに素になるものの個数は、あらかじめQの素因数の積を取ったものを持っておけば高速に求められる。

int T;
ll N,K;

vector<pair<int,int>> D[302020];

int hoge(ll p,int q) {
	int ret=0,i;
	int tp=min(p,(ll)q-1);
	FORR2(a,s,D[q]) ret+=s*(tp/a);
	return ret;
}

pair<ll,ll> hoge2(ll N,ll K) {
	ll L=0,R=1LL*N*N;
	int i;
	while(L+1<R) {
		ll M=(L+R)/2;
		ll tot=0;
		for(i=1;i<=N;i++) tot+=hoge(M*i/N/N,i);
		if(tot>=K) {
			R=M;
		}
		else {
			L=M;
		}
	}
	
	for(i=1;i<=N;i++) {
		ll a=hoge(R*i/N/N,i);
		ll b=hoge(L*i/N/N,i);
		if(a!=b) return {R*i/N/N,i};
	}
	return {0,0};
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=300000;i++) D[i].push_back({1,1});
	
	for(i=2;i<=300000;i++) if(D[i].size()==1) {
		for(j=i;j<=300000;j+=i) {
			x=D[j].size();
			FOR(y,x) D[j].push_back({D[j][y].first*i,-D[j][y].second});
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		ll num=0;
		for(i=1;i<=N;i++) num+=hoge(i,i);
		if(K<=num) {
			pair<ll,ll> p=hoge2(N,K);
			cout<<p.first<<"/"<<p.second<<endl;
		}
		else if(K==num+1) {
			cout<<"1/1"<<endl;
		}
		else if(K<=2*num+1) {
			pair<ll,ll> p=hoge2(N,2*num+2-K);
			cout<<p.second<<"/"<<p.first<<endl;
		}
		else {
			cout<<-1<<endl;
		}
		
	}
}

まとめ

これmの二分探索ではなく小数でやってたら誤差死してたかな…。