HDU-#1108、1713、1722、2028、2504 HDU-GCD+LCM系列

【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;
}