51Nod 2175 ProjectEuler 5 最小公倍数

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

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

$（6=1\times 6=2\times 3=3\times 2）$（6=1×6=2×3=3×2）

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

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

1.3. Input

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

(1<=T<=20)

(1<=N<=20)

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. 解读

$i=1$i=1 时，利用欧几里德算法（辗转相除法），求 $i$i 和 $i+1$i+1 的最大公约数 $gcd$gcd， $i\ast (i+1)$i∗(i+1) 除以最大公约数 $gcd$gcd，即可得到两个数的最小公倍数 $lcm$lcm。

对 $i\in [3,n]$i∈[3,n] ，求 $lcm$lcm 和 $i$i 的最小公倍数，再赋值给 $lcm$lcm，遍历完以后即可求得答案。

3. 代码

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

long long numList[20];

int 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，有问题欢迎通过邮箱交流。