2014
03-23

# Coprime

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.

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

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

3
6 9 1
6 9 2
6 9 3

Case 1: 1
Case 2: 5
Case 3: 7

0<m,n,k<10^9,求与m,n同时互质的第k个正整数(按从小到达顺序排列).

由于所找的数与m,n互质，那么这个数不能含有m,n所包含的素因子。但是考虑到k很大，
不可能一个一个生成。于是想到二分，找到最小的N，使得小于或等于N的数中满足条件的
数的个数大于或等于k.    则，这个最小值即为答案。在判断小于或等于N的数中满足条件的数
的个数时，可用容斥原理找出这些数中是m,n所含质因子倍数的数的个数。N减去所得个数即为
小于或等于N的数中满足条件的数的个数。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef  long long ll;

int flag[40000],prime[40000],pri_num;
int factor[25],fac_num;
ll t,ans,sum,mid;

void get_prime()
{
int i,j;

memset(flag,0,sizeof(flag));
for(i = 2;i*i<40000;i++)
if(flag[i]==0)
for(j = i*i;j<40000;j+=i)
flag[j] = 1;
pri_num = 0;
for(i = 2;i<40000;i++)
if(flag[i]==0)
prime[pri_num++] = i;
}

int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}

void dfs(int set,int num,int kk)
{
int i;

for(i = set;i<=fac_num-num+kk;i++)
{
sum*=factor[i];
if(kk==num-1)
ans+=(mid/sum)*t;
else
dfs(i+1,num,kk+1);
sum/=factor[i];
}
}

int main()
{
int m,n,k,i,j,T,cc;
ll low,high,keep,INF;

cc = 0;
get_prime();
scanf("%d",&T);
INF = 1;
for(i = 1;i<=62;i++)
INF*=2;
while(T--)
{
cc++;
scanf("%d%d%d",&m,&n,&k);
if(m==1&&n==1)
{
printf("Case %d: %d\n",cc,k);
continue;
}
fac_num = 0;
for(i = 0;i<pri_num&&m>=prime[i];i++)
if(m%prime[i]==0)
{
factor[fac_num++] = prime[i];
while(m%prime[i]==0)
m/=prime[i];
}
if(m>1)
factor[fac_num++] = m;
for(i = 0;i<pri_num&&n>=prime[i];i++)
if(n%prime[i]==0)
{
factor[fac_num++] = prime[i];
while(n%prime[i]==0)
n/=prime[i];
}
if(n>1)
factor[fac_num++] = n;
qsort(factor,fac_num,sizeof(factor[0]),cmp);
n = fac_num;
fac_num = 0;
for(i = 1;i<n;i++)
if(factor[i]!=factor[i-1])
factor[fac_num++] = factor[i-1];
factor[fac_num++] = factor[n-1];
low = 1;high = INF;
while(low<=high)
{
mid = high-(high-low)/2;
ans = 0;
t = 1;
for(i = 1;i<=fac_num;i++)
{
sum = 1;
dfs(0,i,0);
t*=-1;
}
ans = mid-ans;
if(ans>=(ll)k)
{
keep = mid;
high = mid-1;
}
else
low = mid+1;
}
printf("Case %d: %I64d\n",cc,keep);
}
return 0;
}

1. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。