hihoCoder [Offer收割]编程练习赛39 C 第K小最简真分数

题目链接http://hihocoder.com/problemset/problem/1655

题意:求与n互质的数中第k小的数是谁。

思路:二分答案,去计算[1,mid]中与n互质的数的个数,我们设为num,如果num>=k,那么令r=mid,反之l=mid+1,这样二分下去就可以找到那个互质的第k小的数,那么问题就在于如何求出[1,mid]中与n互质的个数,这里我们可以直接转化成求[1,mid]中与n不互质的数,然后用区间长度去减就可以了,不互质的个数我们求出n的质因子然后用容斥定理搞搞就可以求出来了,这里回顾了一下容斥定理的两种写法。

dfs版

const int maxn=200000;
ll primes[maxn+5],d[maxn+5];
void init(){
    for (int i=2;i<=maxn;i++){
        if(!primes[i]) primes[++primes[0]]=i;
        for (ll j=1;j<=primes[0] && i*primes[j]<=maxn;j++){
            primes[i*primes[j]]=1;
            if (i%primes[j]==0) break;
        }
    }
}
void dfs(int index,int num,ll x,ll val,ll &ans){
    if (index==d[0]){
        if (!num) return;
        if (num&1) ans+=x/val;
        else ans-=x/val;
        return;
    }
    dfs(index+1,num,x,val,ans);
    dfs(index+1,num+1,x,val*d[index+1],ans);
}
ll sum(ll x){
    ll ans=0;
    dfs(0,0,x,1,ans);
    return x-ans;
}
ll n,k;
int main(){
    init();
    read(n),read(k);
    ll tmp=n;
    for(int i=1;i<=primes[0];i++){
        if(tmp%primes[i]==0){
            d[++d[0]]=primes[i];
            while (tmp%primes[i]==0) tmp/=primes[i];
        }
        if (tmp==1) break;
    }
    ll l=1,r=n,ans;
    while(l<=r){
        ll mid=l+((r-l)>>1);
        ll temp=sum(mid);
        if(temp==k) ans=mid;
        if(temp<k) l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}

位运算版

ll primes[maxn+5],d[maxn+5];
void init(){
    for (int i=2;i<=maxn;i++){
        if(!primes[i]) primes[++primes[0]]=i;
        for (ll j=1;j<=primes[0] && i*primes[j]<=maxn;j++){
            primes[i*primes[j]]=1;
            if (i%primes[j]==0) break;
        }
    }
}
ll sum(ll x){
    ll ans=0;
    int sz=(1<<d[0]);
    for (int i=1;i<sz;i++){
        int tot=0;
        ll val=1;
        for (int j=1;j<=d[0];j++){
            if (i&(1<<(j-1))){
                val*=d[j];
                tot++;
            }
        }
        if (tot&1) ans+=x/val;
        else ans-=x/val;
    }
    return x-ans;
}
ll n,k;
int main(){
    init();
    read(n),read(k);
    ll tmp=n;
    for(int i=1;i<=primes[0];i++){
        if(tmp%primes[i]==0){
            d[++d[0]]=primes[i];
            while (tmp%primes[i]==0) tmp/=primes[i];
        }
        if (tmp==1) break;
    }
    ll l=1,r=n,ans;
    while(l<=r){
        ll mid=l+((r-l)>>1);
        ll temp=sum(mid);
        if(temp==k) ans=mid;
        if(temp<k) l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注