首页 > ACM题库 > HDU-杭电 > HDU 3388-Coprime-最小生成树-[解题报告]HOJ
2014
03-23

HDU 3388-Coprime-最小生成树-[解题报告]HOJ

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

题意:给三个数m,n,k,
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;
}

参考:http://blog.csdn.net/water_water_water/article/details/6723290


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

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