Skip to content

51Nod 2175 ProjectEuler 5#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

6是最小的，1到3所有数的倍数。

2520是最小的，1到10的所有数字的倍数。

输入，输出最小的正整数，他是1到所有数的倍数。

1.3. Input#

输入第一行组数 ，接下来 行，每行一个整数。

1.4. Output#

对于每组数据，输出一个数，表示1到n的最小公倍数。

1.5. Sample Input#

3
3
10
20

1.6. Sample Output#

6
2520
232792560

1.7. Source#

51Nod 2175 ProjectEuler 5

2. 解读#

时，利用欧几里德算法（辗转相除法），求 和 的最大公约数 ， 除以最大公约数 ，即可得到两个数的最小公倍数。

对 ，求 和 的最小公倍数，再赋值给 ，遍历完以后即可求得答案。

3. 代码#

#include <iostream>
#include <string.h>
using namespace std;

long long numList[20];

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

int main()
{
    long long n;
    // 读入n
    scanf("%lld", &n);
    // 初始化数组
    memset(numList, 0, sizeof(numList));
    // 最大公约数buffer
    long long gcdBuffer = 0;
    // 最小公倍数buffer
    long long lcmBuffer = 0;
    // 读入数组
    for (long long i = 0; i < n; i++) {
        // 输入
        scanf("%lld", &numList[i]);
        if (numList[i] > 1) {
            // 辗转相除法
            gcdBuffer = gcd(1, 2);
            // 求最小公倍数
            lcmBuffer = 1 * 2 / gcdBuffer;
            // 循环求最小公倍数
            for (long long j = 3; j <= numList[i]; j++) {
                // 辗转相除法
                gcdBuffer = gcd(lcmBuffer, j);
                // 求最小公倍数
                lcmBuffer = j * lcmBuffer / gcdBuffer;
            }
            // 输出
            printf("%lld\n", lcmBuffer);
        } else {
            // 输出
            printf("%d\n", 1);
        }
    }
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。

Back to top