# Coprime

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 849    Accepted Submission(s): 232

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

#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;
}```

475 篇文章43 人订阅

0 条评论

## 相关文章

### HDU-----（1083）Courses（最大匹配）

Courses Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K ...

2737

### HDU 5651 xiaoxin juju needs help

xiaoxin juju needs help Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

2987

### HDUOJ------1711Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/3...

3046

### HDUOJ---The number of divisors(约数) about Humble Numbers

The number of divisors(约数) about Humble Numbers Time Limit: 2000/1000 MS (Java/O...

3445

### HDU-1520 Anniversary party（树形DP）

Anniversary party Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/...

2884

### HDU-1003 Max Sum(动态规划，最长字段和问题)

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J...

5855

### HDU 3367 Pseudoforest(Kruskal)

Pseudoforest Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/655...

3045

### HDU 3309 Roll The Cube(bfs)

Roll The Cube Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/327...

41513

### HDU 2289 Cup【高精度，二分】

Cup Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

2495

Key Task Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

3554