[2019HDU多校第一场][HDU 6584][G. Meteor]

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6584

题目大意：求所有满足$0<\frac{p}{q}\leq1, gcd(p,q)=1,p\leq n,q\leq n$的分数中，第$k$小的分数

题解：考虑二分答案，并用分数形式记录。假设当前二分的分数为$\frac{p}{q}$，则小于等于这个分数的个数为

$$\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$$

　　　这个式子可以通过预处理莫比乌斯函数的值，然后分块加类欧做到$O(\sqrt{n}logn)$的时间复杂度求解

　　　在二分出答案后，只需找到最小的大于等于$\frac{p}{q}$的分数即可。官方题解使用了$Stern-Brocot Tree$，实际上通过枚举分母也可以做到$O(n)$求解

我的代码跑了7347ms...和之前的A还有K题一样极限_(:з」∠)_

 #include<bits/stdc++.h>

 using namespace std;

 #define N 1000001

 #define LL long long

 LL T,n,k,cnt,p[N],mu[N],v[N];

 #undef LL

 struct Frac

 {

     #define LL __int128

     LL p,q;

     void simp()

       {

       LL d=__gcd(p,q);

       p/=d,q/=d;

       }

     Frac operator +(const Frac &t)const

       {

       Frac tmp;

       tmp.q=q*t.q;

       tmp.p=p*t.q+q*t.p;

       tmp.simp();

       return tmp;

       }

     Frac operator /(const LL &t)const

       {

       Frac tmp;

       tmp.p=p;

       tmp.q=q*t;

       tmp.simp();

       return tmp;

       }

     bool operator <(const Frac &t)const

       {

       return p*t.q<q*t.p;

       }

     bool operator <=(const Frac &t)const

       {

       return p*t.q<=q*t.p;

       }

     #undef LL

 };

 void pretype()

 {

     #define LL long long

     mu[]=;

     for(LL i=;i<N;i++)

       {

       if(!v[i])p[++cnt]=i,mu[i]=-;

       for(LL j=;j<=cnt && i*p[j]<N;j++)

         {

         v[i*p[j]]=;

         if(i%p[j]==)break;

         mu[i*p[j]]=-mu[i];

         }

       }

     for(LL i=;i<N;i++)

       mu[i]+=mu[i-];

     #undef LL

 }

 #define LL __int128

 LL f(LL a,LL b,LL c,LL n)

 {

     LL m=(a*n+b)/c;

     if(!a || !m)return ;

     if(a>=c || b>=c)return n*(n+)/*(a/c)+(b/c)*(n+)+f(a%c,b%c,c,n);

     return n*m-f(c,c-b-,a,m-);

 }

 LL check(Frac k)

 {

     LL res=;

     for(LL i=;i<=n;i++)

       {

       LL j=n/(n/i);

       res+=(mu[j]-mu[i-])*f(k.p,,k.q,n/i);

       i=j;

       }

     return res;

 }

 LL ceil(LL x,LL y){return (x-)/y+;}

 #undef LL

 void Find(Frac k)

 {

     #define LL long long

     Frac ans={,};

     for(LL i=;i<=n;i++)

       ans=min(ans,{ceil(k.p*i,k.q),i});

     ans.simp();

     printf("%lld/%lld\n",(LL)ans.p,(LL)ans.q);

 }

 void init()

 {

     scanf("%lld%lld",&n,&k);

     Frac l={,n},r={,},mid;

     while(l+(Frac){,n*n}<=r)

       {

       mid=(l+r)/;

       if(check(mid)<k)l=mid;

       else r=mid;

       }

     Find(l);

 }

 int main()

 {

     //freopen("test.in","r",stdin);

     //freopen("test.out","w",stdout);

     pretype();

     scanf("%lld",&T);

     while(T--)init();

     return ;

 }

巴特西

[2019HDU多校第一场][HDU 6584][G. Meteor]

最新文章

热门文章