hdu3388 Coprime【容斥原理】

简介: Problem Description Please write a program to calculate the k-th positive integer that is coprime with m and n simultaneously.
Problem Description
Please write a program to calculate the k-th positive integer that is coprime with m and n simultaneously. A is coprime with B when their greatest common divisor is 1.
 

Input
The first line contains one integer T representing the number of test cases.
For each case, there's one line containing three integers m, n and k (0 < m, n, k <= 10^9).
 

Output
For each test case, in one line print the case number and the k-th positive integer that is coprime with m and n.
Please follow the format of the sample output.
 

Sample Input
 
 
3 6 9 1 6 9 2 6 9 3
 
题目翻译:求同时与m,n互质的第k个数是多少!
解题思路:直接求m,n的最小公倍,然后通过二分查找找到第k个数!
不得不说题目数据的严密性,卡超时比较严,直接求m,n的最小公倍其实是花费不了很多时间的,gcd你懂得
但是求m*n的素因子时就不一样了,由于m,n较大,直接遍历m*n势必会花费很多时间,自然没有分开求m的素因子和n的素因子省时间,由于m,n可能存在相同的素因子,那么需要我们处理一下,我采取的是里哟办法set容器,排序去重,由于在set里面对数据的操作不方便,于是又把里面的元素取出放到数组里,接下来就是容斥原理+二分了!

#include <cstdio>
#include <set>
using namespace std;
#define LL long long
LL p[200],top;
set<LL>pp;
void getp(LL m){
    LL i;
    for(i=2,top=0;i*i<=m;i++)
        if(m%i==0){
            pp.insert(i);
            while(m%i==0) m/=i;
        }
    if(m>1) pp.insert(m);
}
void GETP(){
    top = 0;
    while(!pp.empty()){
        p[top++] = *pp.begin();
        pp.erase(pp.begin());
    }
}
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,n;
    int T,q=0;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&m,&n,&k);
        getp(m);
        getp(n);
        GETP();
        LL mid,l=0,r=0x3f3f3f3f3f3f3f3f,t;
        while(l<=r){
            mid=(l+r)>>1;
            t=mid-nop(mid,0);
            if(t>=k) r=mid-1;
            else l=mid+1;
        }
        printf("Case %d: %lld\n",++q,l);
    }
    return 0;
}


目录
打赏
0
0
0
0
2
分享
相关文章
HDU2032杨辉三角
有点强迫症,主函数必须简洁,但是这里的if判断语句很碍眼,自己也并没有想到什么不画蛇添足的方法使代码更加简洁......
1516 0
hdu 2544 最短路
点击打开链接hdu2544 思路:  模板题,求解最短路的四种算法都可以。注意求解最短路时候要处理成无向图 代码: /*Dijkstra*/ #include #include #include #include using nam...
935 0
HDU 1248 寒冰王座(完全背包裸题)
寒冰王座 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17092    Accepted Submission(s): 8800 ...
1227 0
hdu 1963 Investment(完全背包)
点击打开链接hdu 1963 思路: 完全背包 分析: 1 根据题目很容易分析出题目是裸的完全背包,但是经过题目的条件我们发现dp数组开不下(怒RE不解释) 2 然后发现题目说了所有的bonds的value都是1000的整数倍,因此这边我...
868 0
HDU-1370,Biorhythms(中国剩余定理)
本题主要就是应用中国剩余定理。
HDOJ/HDU 2560 Buildings(嗯~水题)
HDOJ/HDU 2560 Buildings(嗯~水题)
125 0
HDOJ/HDU 2560 Buildings(嗯~水题)
HDOJ(HDU) 2090 算菜价(简单水题、)
HDOJ(HDU) 2090 算菜价(简单水题、)
193 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等