hdu6584
题目本质上是 找分子分母小于n的第k小的真分数,我们直接对答案二分即可，采取分数二分的方式，找到一个区间，它包含最多一个解
我们一直往下二分，直到区间足够小，最后用 Stern-Brocot Tree 或 法雷序列找出答案
$$
\begin{aligned}
&答案肯定是找到一个分子分母小于n的分数\frac{p}{q}他满足下面的特征\\
&(\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1][\frac{i}{j} \leq \frac{p}{q}]) = k\\
&我们对左式化简\\
&=\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1][i \leq \frac{p}{q}j]\\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n[gcd(i,j)=1]\\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^ne(gcd(i,j))\\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n(u*1)(gcd(i,j))\\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n\sum_{d|gcd(i,j)}u(d)*1(d)\\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n\sum_{d|gcd(i,j)}u(d)\\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n\sum_{d|i,d|j}u(d)\\
&=\sum_{d=1}^{n}u(d)\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n[d|i,d|j]\\
&=\sum_{d=1}^{n}u(d)\sum_{xd=1}^{\lfloor \frac{p}{q}(yd)\rfloor}\sum_{yd=1}^n[d|(xd),d|(yd)]\\
&=\sum_{d=1}^{n}u(d)\sum_{x=1}^{\lfloor\frac{\lfloor
\frac{p}{q}(yd)\rfloor}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}1\\
&=\sum_{d=1}^{n}u(d)\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{\lfloor
\frac{p}{q}(yd)\rfloor}{d}\rfloor\\
&=\sum_{d=1}^{n}u(d)\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}{\lfloor \frac{p}{q}y\rfloor}\\
\end{aligned}
$$
这里是可以求出答案的,对d分块，右边的部分采用类欧几里得算法我们一直往下二分，直到区间足够小，最后用 Stern-Brocot Tree 或 法雷序列找出答案
#include<bits/stdc++.h> using namespace std; typedef long long ll; /**** * 超级积性函数线性筛 * ****/ typedef long long ll; const ll maxn=2e6+10; ll no_pri[maxn]={0,1,0},pri[maxn],low[maxn]; ll PHI[maxn],DDD[maxn],XDX[maxn],MUU[maxn],SIG[maxn]; void f_ini(){ for(ll i=2;i<maxn;i++){ if(!no_pri[i]) low[i]=pri[++pri[0]]=i; for(ll j=1;pri[j]*i<maxn;j++){ no_pri[pri[j]*i]=1; if(i%pri[j]==0) { low[pri[j]*i]=low[i]*pri[j]; break; } else low[pri[j]*i]=pri[j]; } } DDD[1]=PHI[1]=MUU[1]=SIG[1]=1;// 改这里 for(ll i=1;i<=pri[0];i++){ for(ll mul=pri[i],ct=1;mul<maxn;mul*=pri[i],ct++){ DDD[mul]=ct+1;// 改这里 SIG[mul]=SIG[mul/pri[i]]+mul;// 改这里 MUU[mul]=ct==1?-1:0;// 改这里 PHI[mul]=mul/pri[i]*(pri[i]-1);// 改这里 } } for(ll i=2;i<maxn;i++){ for(ll j=1;pri[j]*i<maxn;j++){ ll x=low[i*pri[j]], y=i*pri[j]/x; DDD[x*y]=DDD[x]*DDD[y]; MUU[x*y]=MUU[x]*MUU[y]; PHI[x*y]=PHI[x]*PHI[y]; SIG[x*y]=SIG[x]*SIG[y]; if(i%pri[j]==0) break; } } for(ll i=1;i<maxn;i++) { DDD[i]+=DDD[i-1]; MUU[i]+=MUU[i-1]; PHI[i]+=PHI[i-1]; SIG[i]+=SIG[i-1]; XDX[i]=(DDD[i]-DDD[i-1])*i+XDX[i-1]; } } struct frac{ ll x,y; frac(ll x_=0,ll y_=1){ ll gcd=__gcd(x_,y_); x=x_/gcd; y=y_/gcd; } frac operator +(const frac&rhs){ ll lcm=y/__gcd(y,rhs.y)*rhs.y; return frac(x*(lcm/y)+rhs.x*(lcm/rhs.y),lcm); } frac operator /(ll k){ ll gcd=__gcd(k,x); return frac(x/gcd,y*(k/gcd)); } bool operator <=(const frac&rhs){ ll lcm=y/__gcd(y,rhs.y)*rhs.y; return x*(lcm/y)<=rhs.x*(lcm/rhs.y); } }; // a>=0 b>=0 c>0 n>=0 -> O(lg(a,c)) void calfgh(ll a,ll b,ll c,ll n,ll&f,ll&g,ll&h){ ll A=a/c,B=b/c,s0=n+1,s1=n*(n+1)/2,s2=n*(n+1)*(2*n+1)/6; f=s1*A+s0*B; g=s2*A+s1*B; h=s2*A*A+s0*B*B+2*s1*A*B-2*B*f-2*A*g;// 先减掉 a%=c,b%=c; ll m=(a*n+b)/c; if(m!=0) { ll ff,gg,hh; calfgh(c,c-b-1,a,m-1,ff,gg,hh); f+=n*m-ff; g+=(n*m*(n+1)-hh-ff)/2; h+=n*m*m-2*gg-ff; } h+=2*B*f+2*A*g;//再加上 } ll count(frac k,int n){ ll ret=0; for(int i=1,ed;i<=n;i=ed+1){ ed=n/(n/i); ll a[3]; calfgh(k.x,0,k.y,n/i,a[0],a[1],a[2]); ret+=1ll*(MUU[ed]-MUU[i-1])*a[0]; } return ret; } int main(){ f_ini(); ll t,n,k; scanf("%lld",&t); while(t--){ scanf("%lld%lld",&n,&k); frac l(0,1),r(1,1);// [l,r] for(int ijk=0;ijk<40;ijk++){ frac mid=(l+r)/2; ll ct=count(mid,n);//[0,mid] if(ct>=k)r=mid; else l=mid; } //[l,r] frac L(0,1),R(1,0); while(true){ frac mid(L.x+R.x,L.y+R.y); if(mid.x<=n&&mid.y<=n&&l<=mid&&mid<=r){ printf("%lld/%lld\n",mid.x,mid.y); break; } if(!(l<=mid)){ L=mid; } if(!(mid<=r)){ R=mid; } } } }
