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).
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.
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;
}
