Title Link: http://acm.hdu.edu.cn/showproblem.php?pid=6584

Main idea of the question: find all the scores that satisfy \ (0 < \ frac {P} {Q} \ leq1, GCD (P, q) = 1, P \ Leq n, Q \ Leq n \), the smaller of \ (k \)

Question solution: consider the two-point answer and record it in the form of score. If the current binary score is \ (\ frac{p}{q} \), the number of scores less than or equal to this score is

$$\sum_{i=1}^{n}\sum_{j=1}^{\left \lfloor \frac{pi}{q} \right \rfloor}[gcd(i,j)==1]=\sum_{i=1}^{n}\sum_{j=1}^{\left \lfloor \frac{pi}{q} \right \rfloor}\sum_{d|i,d|j}^{ }\mu(d)=\sum_{i=1}^{n}\sum_{d|i}^{ }\mu(d)\left \lfloor \frac{pi}{qd} \right \rfloor=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\left \lfloor \frac{pi}{q} \right \rfloor$$

In this formula, the time complexity of \ (O(\sqrt{n}logn) \) can be solved by preprocessing the value of Mobius function, and then adding the similar Europe into blocks.

After bisecting the answer, just find the minimum score greater than or equal to \ (\ frac{p}{q} \). The official solution uses \ (stern brocot tree \), which can be solved by enumerating denominators.

My code ran 7347ms... The same limit as the previous A and K questions._

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 1000001
  4 #define LL long long
  5 LL T,n,k,cnt,p[N],mu[N],v[N];
  6 #undef LL
  7 struct Frac
  8 {
  9     #define LL __int128
 10     LL p,q;
 11     void simp()
 12       {
 13       LL d=__gcd(p,q);
 14       p/=d,q/=d;
 15       }
 16     Frac operator +(const Frac &t)const
 17       {
 18       Frac tmp;
 19       tmp.q=q*t.q;
 20       tmp.p=p*t.q+q*t.p;
 21       tmp.simp();
 22       return tmp;
 23       }
 24     Frac operator /(const LL &t)const
 25       {
 26       Frac tmp;
 27       tmp.p=p;
 28       tmp.q=q*t;
 29       tmp.simp();
 30       return tmp;
 31       }
 32     bool operator <(const Frac &t)const
 33       {
 34       return p*t.q<q*t.p;
 35       }
 36     bool operator <=(const Frac &t)const
 37       {
 38       return p*t.q<=q*t.p;
 39       }
 40     #undef LL
 41 };
 42 void pretype()
 43 {
 44     #define LL long long
 45     mu[1]=1;
 46     for(LL i=2;i<N;i++)
 47       {
 48       if(!v[i])p[++cnt]=i,mu[i]=-1;
 49       for(LL j=1;j<=cnt && i*p[j]<N;j++)
 50         {
 51         v[i*p[j]]=1;
 52         if(i%p[j]==0)break;
 53         mu[i*p[j]]=-mu[i];
 54         }
 55       }
 56     for(LL i=1;i<N;i++)
 57       mu[i]+=mu[i-1];
 58     #undef LL
 59 }
 60 #define LL __int128
 61 LL f(LL a,LL b,LL c,LL n)
 62 {
 63     LL m=(a*n+b)/c;
 64     if(!a || !m)return 0;
 65     if(a>=c || b>=c)return n*(n+1)/2*(a/c)+(b/c)*(n+1)+f(a%c,b%c,c,n);
 66     return n*m-f(c,c-b-1,a,m-1);
 67 }
 68 LL check(Frac k)
 69 {
 70     LL res=0;
 71     for(LL i=1;i<=n;i++)
 72       {
 73       LL j=n/(n/i);
 74       res+=(mu[j]-mu[i-1])*f(k.p,0,k.q,n/i);
 75       i=j;
 76       }
 77     return res;
 78 }
 79 LL ceil(LL x,LL y){return (x-1)/y+1;}
 80 #undef LL
 81 void Find(Frac k)
 82 {
 83     #define LL long long
 84     Frac ans={1,1};
 85     for(LL i=1;i<=n;i++)
 86       ans=min(ans,{ceil(k.p*i,k.q),i});
 87     ans.simp();
 88     printf("%lld/%lld\n",(LL)ans.p,(LL)ans.q);
 89 }
 90 void init()
 91 {
 92     scanf("%lld%lld",&n,&k);
 93     Frac l={1,n},r={1,1},mid;
 94     while(l+(Frac){1,n*n}<=r)
 95       {
 96       mid=(l+r)/2;
 97       if(check(mid)<k)l=mid;
 98       else r=mid;
 99       }
100     Find(l);
101 }
102 int main()
103 {
104     //freopen("test.in","r",stdin);
105     //freopen("test.out","w",stdout);
106     pretype();
107     scanf("%lld",&T);
108     while(T--)init();
109     return 0;
110 }