倍约数类问题算法的优化

摘要：优化

原题来自蓝桥杯：

题目描述

已知正整数a0,a1,b0,b1。设某未知正整数x 满足：
1． x 和a0 的最大公约数是a1；
2． x 和 b0 的最小公倍数是 b1。
求解满足条件的 x 的个数

重要结论

两个需要知道的关于最大公约数和最小公倍数的结论。

• 最大公约数：如果gcd(x,y)=z，那么gcd(x/z,y/z)=1

• 最小公倍数：lcm(x,y)=z

  ①如果lcm(x,y)=z，那么gcd(z/y,z/x)=1。
  这个我们来证明一下：我们设lcm(x,y)=z，那么lcm(x,y)=x*y/gcd(x,y)=z，所以gcd(x,y)=x*y/z。由最大公约数结论可得，gcd(z/y,z/x)=1。

  ②如果y是x的公倍数，则x是y的因数，也就是y % x == 0。
  由上面几条结论可得，x一定是b1的因数，而且x % a1 == 0，gcd(x/a1 ,a0/a1) == 1，gcd(b1/b0 ，b1/x) == 1。
  那么我们就可以枚举b1的因数，然后判断了

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


n = int(input())

while n:
    a0, a1, b0, b1 = map(int, input().split())
    x_num = 0
    p = a0 / a1
    q = b1 / b0

    x = 1
    while x * x <= b1:
        if b1 % x == 0:
            if x % a1 == 0 and gcd(x / a1, p) == 1 and gcd(q, b1 / x) == 1:
                x_num += 1
            y = b1 / x
            if x == y:
                continue
            if y % a1 == 0 and gcd(y / a1, p) == 1 and gcd(q, b1 / y) == 1:
                x_num += 1

        x += 1

    print(x_num)

    n -= 1