ACM模版

描述

题解

GCD!!!水题……一开始想暴力,后来发现会超时,原来是一个 GCD 啊。

这里首先我们需要找到 x 和 i 的最小公倍数,然后用这个最小公倍数除以 x 即可。
所以,假设 gd 是 x 和 i 的最大公约数,那么最小公倍数为 xi/gd ,所以最后结果为 i/gd

是不是很简单,对啊,这么简单的题一开始我竟然 TLE 了!!!闭门思过去……

代码

#include <iostream>

using namespace std;

long long gcd(long long x, long long y)
{
    if (!x || !y)
    {
        return x > y ? x : y;
    }
    for (long long t; t = x % y, t; x = y, y = t);
    return y;
}

int main(int argc, const char * argv[])
{
    long long x, n;
    while (cin >> x >> n)
    {
        for (int i = 2; i <= n; i++)
        {
            long long gd = gcd(x, i);
            long long cnt = i / gd;
            cout << cnt << '\n';
        }
    }

    return 0;
}