POJ 2773 Happy 2006

Description

Input

Output

Sample Input

2006 1
2006 2
2006 3

Sample Output

1
3
5

Source

题目大意：

给定m,k，问你第K个与m互质的数是多少？  其中  m (1 <= m <= 1000000), K (1 <= K <= 100000000).

解题思路：

用位运算的容斥原理，计算 [1，x]与m互质的数的方法是：

    假设 m的质因数为 a,b,c ，那么与m不互斥的数个数为 f(a)+f(b)+f(c)-f(ab)-f(ac)-fa(bc)+f(abc)，f(t)的含义是 (1,x)有多少个数与t不互质，很明显f(t)=x/t，那么与m互斥的数个数很明显为x-( f(a)+f(b)+f(c)-f(ab)-f(ac)-fa(bc)+f(abc)).

因此只要二分求出刚好大于等于K的这个数就是答案。

解题代码：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
const int maxn=1100000;
int m,n;
vector <int> v;
vector <int> t;
bool f[maxn];

void getPrime(){
    for(int i=0;i<maxn;i++) f[i]=true;
    for(int i=4;i<maxn;i+=2) f[i]=false;
    for(int i=3;i<maxn;i+=2){
        for(int j=i;j<maxn/i;j+=2){
            f[i*j]=false;
        }
    }
    for(int i=2;i<maxn;i++){
        if(f[i]) v.push_back(i);
    }
}

void getsubPrime(){
    t.clear();
    int s=0,now=m;
    while(now>=v[s]){
        if(now%v[s]==0){
            t.push_back(v[s]);
            while(now%v[s]==0){
                now/=v[s];
            }
        }
        s++;
    }
}

ll get(ll y){
    ll ans=0;
    for(int i=0;i<(1<<t.size());i++){
        int cnt=0,sum=1;
        for(int k=0;k<t.size();k++){
            if( i& (1<<k) ){
                sum*=t[k];
                cnt++;
            }
        }
        if(cnt%2==0) ans+=y/sum;
        else ans-=y/sum;
    }
    return ans;
}

void solve(){
    getsubPrime();
    ll l=0,r=1e17;
    while(l<r){
        ll mid=(l+r)/2;
        if(get(mid)>=n) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
}

int main(){
    getPrime();
    while(scanf("%d%d",&m,&n)!=EOF){
        solve();
    }
    return 0;
}

POJ 2773 Happy 2006,,5-wow.com