HDU 3388 Coprime（容斥原理+二分）

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

Sample Output

Case 1: 1

Case 2: 5

Case 3: 7


这里有两个数n,m;这里用容斥原理同样可以求在1到任意范围内，和n,m两个数互质的个数。把n,m分别分解质因数，然后把相同的合并
和求一个数的本质没什么区别，套模版。然后就要去找最小的数x使得1到x与n，m互质的个数等于k，x就是答案。用二分去找n，上限直接设成
1<<62

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#include <stdio.h>

#include <algorithm>

using namespace std;

typedef long long int LL;

const LL INF=(LL)1<<62;

#define MAX 1000000

bool check[MAX+5];

LL prime[MAX+5];

LL sprime[MAX+5];

LL q[MAX+5];

LL n,m,k,cnt;

void eular()//线性筛

{

    memset(check,false,sizeof(check));

    int tot=0;

    for(int i=2;i<=MAX+5;i++)

    {

        if(!check[i])

            prime[tot++]=i;

        for(int j=0;j<tot;j++)

        {

            if(i*prime[j]>MAX+5) break;

            check[i*prime[j]]=true;

            if(i%prime[j]==0) break;

        }

    }

}

void Divide(LL n,LL m)

{

    cnt=0;

    LL t=(LL)sqrt(1.0*n);

    for(LL i=0;prime[i]<=t;i++)

    {

        if(n%prime[i]==0)

        {

            sprime[cnt++]=prime[i];

            while(n%prime[i]==0)

                n/=prime[i];

        }

    }

    if(n>1)

        sprime[cnt++]=n;

     t=(LL)sqrt(1.0*m);

    for(LL i=0;prime[i]<=t;i++)

    {

        if(m%prime[i]==0)

        {

            sprime[cnt++]=prime[i];

            while(m%prime[i]==0)

                m/=prime[i];

        }

    }

    if(m>1)

        sprime[cnt++]=m;

}

LL Ex(LL n)//容斥原理

{

    LL sum=0,t=1;

    q[0]=-1;

    for(LL i=0;i<cnt;i++)

    {

        LL x=t;

        for(LL j=0;j<x;j++)

        {

            q[t]=q[j]*sprime[i]*(-1);

            t++;

        }

    }

    for(LL i=1;i<t;i++)

        sum+=n/q[i];

    return sum;

}

LL Binary()

{

    LL l=1,r=INF;

    LL ans,mid;

    while(l<=r)

    {

        mid=(l+r)/2;

        if((mid-Ex(mid))>=k)

        {

            ans=mid;

            r=mid-1;

        }

        else

            l=mid+1;

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    int cas=0;

    eular();

    while(t--)

    {

        scanf("%lld%lld%lld",&m,&n,&k);

        if(n==1&&m==1)

        {

            printf("Case %d: %lld\n",++cas,k);

            continue;

        }

        Divide(n,m);

        sort(sprime,sprime+cnt);

        int cot=1;

        for(LL i=1;i<cnt;i++)

        {

            if(sprime[i]!=sprime[i-1])

            {

                sprime[cot++]=sprime[i];

            }

        }

        cnt=cot;

        printf("Case %d: %lld\n",++cas,Binary());

    }

    return 0;

}