描述
题解
GCD!!!水题……一开始想暴力,后来发现会超时,原来是一个 GCD 啊。
这里首先我们需要找到 x 和 i 的最小公倍数,然后用这个最小公倍数除以 x 即可。
所以,假设 gd 是 x 和 i 的最大公约数,那么最小公倍数为 x∗i/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;
}