KafuuMegumi's Kingdom > hdu 2019 Multi-University Training Contest 2 Meteor

hdu 2019 Multi-University Training Contest 2 Meteor

2019-07-26

二分, 莫比乌斯反演

题目:

给出n,k,求分子分母都不大于n的第k小分数.(n<=1e6,保证答案在(0,1])

解题思路:

对于一个值k,我们可以通过如下推导得出分子分母都不大于n并且小于等于k的分数个数题目.然后可以通过类欧和分块求出这个值.至于k可以二分求得.问题现在变成对于一个k找到一个小于等于k并且分子分母都不大于n的最大分数,可以枚举分母然后即可贪心求得满足条件的最大分子,最后维护一下最大值即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct frac{
    ll p,q;
    frac operator+(const frac&x)const{
        frac tmp;
        tmp.q=q/__gcd(q,x.q)*x.q;
        tmp.p=p*(tmp.q/q)+x.p*(tmp.q/x.q);
        return tmp;
    }
    frac operator/(const int x)const{
        frac tmp;
        tmp.p=p;
        tmp.q=q*x;
        ll g=__gcd(tmp.p,tmp.q);
        tmp.p/=g;tmp.q/=g;
        return tmp;
    }
    bool operator<(const frac &x)const{
        return p*x.q<q*x.p;
    }
};
const int N=1e6+5;
ll mu[N],tot,p[N],sum_mu[N];
bool v[N];
void moblus(){
    memset(v,0,sizeof v);
    mu[1]=1;tot=0;
    for(int i=2;i<N;i++){
        if(!v[i])p[tot++]=i,mu[i]=-1;
        for(int j=0;i*p[j]<N&&j<tot;j++){
            v[i*p[j]]=1;
            if(i%p[j])mu[i*p[j]]=-mu[i];
            else{
                mu[i*p[j]]=0;
                break;
            }
        }
    }
    sum_mu[0]=0;
    for(int i=1;i<N;i++)sum_mu[i]=sum_mu[i-1]+mu[i];
}
ll f(ll a,ll b,ll c,ll n){
    if(!a)return 0;
    if(a>=c||b>=c){
        return n*(n+1)/2*(a/c)+b/c*(n+1)+f(a%c,b%c,c,n);
    }
    ll m=(a*n+b)/c;
    return n*m-f(c,c-b-1,a,m-1);
}
ll calc(const frac&x,ll n){
    ll res=0;
    for(int i=1;i<=n;){
        int j=n/(n/i);
        res+=(sum_mu[j]-sum_mu[i-1])*f(x.p,0,x.q,n/i);
        i=j+1;
    }
    return res;
}
frac find(const frac&x,ll n){
    frac tmp={1,1};
    for(int i=1;i<=n;i++){
        tmp=min(tmp,(frac){(x.p*i)/x.q+1,i});
    }
    ll g=__gcd(tmp.p,tmp.q);
    tmp.p/=g;tmp.q/=g;
    return tmp;
}
int main(){
    moblus();
    int T;
    scanf("%d",&T);
    for(;T--;){
        ll n,k;
        scanf("%lld%lld",&n,&k);
        frac L={0,1},R={1,1};
        for(int i=0;i<=40;i++){
            frac mid=(L+R)/2;
            ll cnt=calc(mid,n);
            if(cnt<k){
                L=mid;
                if(cnt==k-1)break;
            }
            else R=mid;
        }
        frac ans=find(L,n);
        printf("%lld/%lld\n",ans.p,ans.q);
    }
}