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

柔情只为你懂 2021-11-01 06:10 352阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6584][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题一样极限\_(:з」∠)\_

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/DeaphetS/p/11229431.html

[http_acm.hdu.edu.cn_showproblem.php_pid_6584]: http://acm.hdu.edu.cn/showproblem.php?pid=6584
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/2f7dd7bbe40848c0b68673569614486f.png