淘先锋技术网

首页 1 2 3 4 5 6 7

      【GCD+LCM系列】:最小公倍数和最大公约数在求解中是非常重要的,这里将HDU上的几道基础题归纳一下。持续更新中.....

       #1108:最小公倍数

      题目大意:给定两个正整数,计算这两个数的最小公倍数。

      解题思路:直接就一个gcd+lcm就出来了哈,很简单的模板了。关于这两个的推导网上有很多资料,自己模拟一下也可以得到,就不赘述了,详见code。

      题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1108

     code:

#include <iostream>
#include <cstdio>
using namespace std;

int n,m,ans;

int gcd(int a,int b){
    return b==0 ? a : gcd(b,a%b);
}

int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        ans=lcm(n,m);
        printf("%d\n",ans);
    }
    return 0;
}

      #1722:Cake

      题目大意:给你一块蛋糕,最少要切成多少份(不一样大小)?使得来p或者q个人都能平均分配。

      解题思路:首先通过测试用例可以发现分法与来的人相关。因此我们假设来p个人,则要切p刀,来q个人同理可得。而中间可能有重复的切法。因此,切法就是p+q再减去他们的最大公约数的数量。详见code。

      题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1722

      code:

#include <iostream>
#include <cstdio>
using namespace std;

int p,q;

int gcd(int a,int b){
    return b==0 ? a : gcd(b,a%b);
}

int main(){
    while(scanf("%d%d",&p,&q)!=EOF){
        printf("%d\n",p+q-gcd(p,q));
    }
    return 0;
}

       #2028:Lowest Common Multiple Plus

       题目大意:求多个数的最小公倍数。

       解题思路:很裸的一道最小公倍数的题,直接由gcd(a,b)*lcm(a,b)=a*b可得:最小公倍数lcm(a,b)=a/gcd(a,b)*b。这里要注意的是要先除再乘,防止a*b发生溢出。详见code。

       题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=2028

       code:

#include <iostream>
#include <cstdio>
using namespace std;

int n,num,ans;

int GCD(int a,int b){
    return b==0 ? a : GCD(b,a%b);
}

int LCM(int a,int b){
    return a/GCD(a,b)*b;//先除后乘
}

int main(){
    while(scanf("%d",&n)!=EOF){
        ans=1;
        for(int i=0;i<n;i++){
            scanf("%d",&num);
            ans=LCM(ans,num);
        }
        printf("%d\n",ans);
    }
    return 0;
}

     #2504:又见GCD

    题目大意:已知a,c的最大公约数为b,给出a,求最小的c。

    解题思路:由性质可知,c的范围为(b,a*b),因此直接遍历这个区间的元素,求解各个元素与a的最大公约数,如等于b则输出跳出。

    题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=2504

   code:

#include <iostream>
#include <cstdio>
using namespace std;

int a,b,t;

int gcd(int x,int y){
    return y==0 ? x : gcd(y,x%y);
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&a,&b);
        for(int i=b+1;i<=b*a;i++)
            if(gcd(a,i)==b) {printf("%d\n",i);break;}
    }
    return 0;
}

      #1713:相遇周期

      题目大意:给出两颗卫星的运行圈数需要的天数,求相遇的最小周期。

      解题思路:开始想了很久怎样计算周期,找不到其相遇的起始点。后边才发现是求分数的最小公倍数的问题。求两个分数的a/b,c/d的最小公倍数,假设其为x/y,则分子的x要尽量小,即为lcm(a,c),分母要尽量大,即为gcd(b,d)。考虑整除的情况为,分母互质时,其通分后,计算后的结果肯定整除,则结果直接为分子的最小公倍数。否则为分子的最小公倍数除以分母的最大公约数。详见code。

      题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1713

     code:

#include <iostream>
#include <cstdio>
using namespace std;

int a,b,c,d,t;

int gcd(int a,int b){
    return b==0 ? a : gcd(b,a%b);
}

int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d/%d",&a,&b);
        scanf("%d/%d",&c,&d);
        int e=gcd(a,b); //第一个分数的最大公约数
        a/=e;b/=e;  //化简分数
        int f=gcd(c,d); //第二个分数的最大公约数
        c/=f;d/=f;  //化简分数
        if(gcd(b,d)==1) printf("%d\n",lcm(a,c)); //如果分母互质,则为分子的最小公倍数
        else printf("%d/%d\n",lcm(a,c),gcd(b,d)); //否则为分子的最小公倍数,分母的最大公约数
    }
    return 0;
}