2009年NOIP提高组真题-HanKson的趣味题（GCD&LCM优化）

本题的编码是用Python实现的，C++的思路也是相同的。

希望本文能够帮助到你！

题目：

暴力法：

直接根据题目的要求写：

from math import gcd

def lcm(a, b):

    return a*b//gcd(a, b)

n = int(input())

for _ in range(n):

    cnt = 0

    a0, a1, b0, b1 = map(int, input().split())

    for x in range(1, b1 + 1):

        # 如果b1不能被x整除，x肯定不满足要求。

        if b1 % x != 0: continue

        if gcd(x, a0) == a1 and lcm(x, b0) == b1:

            cnt += 1

    print(cnt)

代码中有个小细节：

# 如果b1不能被x整除，x肯定不满足要求。

if b1 % x != 0: continue

这样可以减少一些不必要的计算。

根据题意，时间复杂度大概是O(n**2)，具体一点数据量会达到百亿级别️

而python本来就比较慢，暴力写法必定会跑不出来，必须要进行优化才行。

优化：

由题意知：x和b0的最大公倍数是b1，我们假设一个y，x * y == b1，y可能是答案。优化如下：

from math import gcd

def lcm(a, b):

    return a*b//gcd(a, b)

n = int(input())

for _ in range(n):

    cnt = 0

    a0, a1, b0, b1 = map(int, input().split())

    # 1 <= x <= sqrt(b1) <= y <= b1

    # x, y 可以取到1到b1的所有值。

    for x in range(1, int(b1**0.5)+1):

        if b1 % x != 0: continue

        y = b1 // x

        if gcd(x, a0) == a1 and lcm(x, b0) == b1:

            cnt += 1

        # 如果该数已经被判断过则跳过。

        if x == y: continue

        if gcd(y, a0) == a1 and lcm(y, b0) == b1:

            cnt += 1

    print(cnt)

具体的GCD和LCM手写法可以看这篇文章

若出现错误，欢迎指出。

祝大家在学习的道路上能取得大的进步！

2009年NOIP提高组真题-HanKson的趣味题（GCD&LCM优化）的相关教程结束。