已知正整数 a0,a1,b0,b1,设某未知正整数 x 满足: 1. x 和 a0 的最大公约数是 a1 2. x 和 b0 的最小公倍数是 b1 求解满足条件的 x 的个数。请你帮助他编程求解这个问题。 对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000。
时间: 2023-07-14 21:12:21 浏览: 99
这道题目可以使用数学方法求解。
首先,我们可以根据题目中的条件列出以下两个式子:
1. x = k * a1 - a0
其中 k 是任意正整数,因为 k 增加 1,x 会加上 a1,所以 x 和 a1 的最大公约数仍然是 a1。
2. x = b1 / gcd(b0, x) * x
根据最小公倍数的定义可得,b1 是 x 和 b0 的最小公倍数,即 b1 是 gcd(b0, x) 和 lcm(b0, x) 的乘积。因为 x 和 gcd(b0, x) 的最大公约数是 gcd(b0, x),所以我们可以将上式改写为:
x = lcm(b0, x) * (b1 / gcd(b0, x)) / b0
因为 gcd(b0, x) 是 x 的因子,所以 lcm(b0, x) / gcd(b0, x) 是 x 的另一个因子,于是我们可以将上式改写为:
x = k * lcm(b0, x)
其中 k = b1 / (b0 * lcm(b0, x) / gcd(b0, x))
现在我们需要求解 x = k * lcm(b0, x) 的正整数解个数。设 lcm(b0, x) = t,则有:
x = k * t
lcm(b0, x) = t = b0 * x / gcd(b0, x)
代入原式得:
x = k * b0 * x / gcd(b0, x)
移项得:
gcd(b0, x) = k * b0
因为 x 和 b0 互质时有 gcd(b0, x) = 1,所以 k 的值必须是 b0 的因子。我们可以枚举 b0 的因子 k,然后检查 k * b0 是否是 x 和 a0 的最大公约数的因子,如果是,则满足条件。
至此,我们就求出了满足条件的 x 的个数。时间复杂度为 O(σ(b0) + d(b0)),其中 σ(b0) 表示 b0 的因子个数,d(b0) 表示 b0 的因子之和。
阅读全文