poj 2773 Happy2006【容斥原理】

简介: Happy 2006 Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 9936   Accepted: 3411 Description Two positive i...
Happy 2006
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 9936   Accepted: 3411

Description

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006. 

Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order. 

Input

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).

Output

Output the K-th element in a single line.

Sample Input

2006 1
2006 2
2006 3

Sample Output

1
3
5
题目翻译:给出m,k,求第k个和m互质的数字!
解题思路:数据量较大,因此全部采用long long,想求出第k个互质的数,数据量太大,因此采用2分查找,来找d第K个数字,想知道当前数字t是第几个与m的互质的数,需要求出t前有几个与m不互质的数字,利用容斥原理,可以解决,然后对比即可!
 
#include<cstdio>
#define LL long long
LL p[20],top;
void getp(LL m){
    LL i;
    for(i=2,top=0;i*i<=m;i++)
        if(m%i==0){
            p[top++]=i;
            while(m%i==0) m/=i;
        }
    if(m>1) p[top++]=m;
}
LL nop(LL mid,LL t){
    LL i,sum=0;
    for(i=t;i<top;i++)
        sum+=mid/p[i]-nop(mid/p[i],i+1);
    return sum;
}
int main(){
    LL k,m;
    while(scanf("%lld%lld",&m,&k)==2){
        LL mid,l=0,r=0x3f3f3f3f3f3f3f3f,t,ans=0;
        getp(m);
        while(l<=r){
            mid=(l+r)>>1;
            t=mid-nop(mid,0);
            if(t>=k){
                r=mid-1;
                if(t==k) ans=mid;
            }
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
目录
相关文章
|
存储
poj 3254 Corn Fields (状态压缩dp)
状态压缩dp其实就是用二进制来表示所有的状态,比如这题, 我们在某一行可以这样取0 1 0 1 1 0 1,用1代表取了,0代表没取,因为这点,它的数据量也限制在20以内,所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据,所有状态的总数必然很庞大,而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况,我们可以用二进制的一位来表示,0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45,如果我们想要枚举6个点的所有状态,我们只需要从0到2^6取其二进制就可以了,并不会重复或是多余。
31 0
hdu 1052 Tian Ji -- The Horse Racing【田忌赛马】(贪心)
hdu 1052 Tian Ji -- The Horse Racing【田忌赛马】(贪心)
49 0
|
图形学 C++
ZOJ1117 POJ1521 HDU1053 Huffman编码
Huffman编码的思想就是贪心,我们这里使用stl里的优先队列,priority_queue使用堆进行优化,虽然自己也可以写一个堆,但我感觉对于这道题有点主次不分了,再次感觉到stl确实是一个很强大的东西。
50 0
|
人工智能
POJ 3104 Drying
POJ 3104 Drying
|
算法
POJ3061 Subsequence
POJ3061 Subsequence
UVa668 - Parliament(贪心)
UVa668 - Parliament(贪心)
55 0
POJ 2487 Stamps
POJ 2487 Stamps
103 0
|
测试技术
poj-1218 THE DRUNK JAILER 喝醉的狱卒
自己去看看原题; 题目大意: 就是一个狱卒喝醉了,他第一趟吧所有的监狱都带开,第二趟把能把二整除的监狱关闭,第三趟操作能把三整除的监狱; 求最后能逃跑的罪犯数 输入第一个数是代表 测试数据组数 每个数据代表狱卒来回的次数 当作开关问题即可 #include using names...
1003 0
|
人工智能
POJ 1936 All in All
Description You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way.
789 0