有一天,又是dp小王子又是偷偷摸摸的找到了松哥:有两个数p,q,已知他们的最大公约数是x,最小公倍数是y,你知道一共有几组(p,q)满足条件嘛?松哥又要向你请教了。
时间: 2024-04-01 08:36:41 浏览: 90
ansj_seg_lanjing:ansj_seg + lucene by 松哥
根据数学知识,可以得到以下公式:
p * q = x * y
又因为 x 是 p 和 q 的最大公约数,所以 x 一定是 p 和 q 的因数,即 p = x * a,q = x * b(a 和 b 互质)。
将 p 和 q 代入上式得到:
x * a * x * b = x * y
化简得:
a * b = y / x
由于 a 和 b 互质,所以 y / x 必须是一个完全平方数的积,即 y / x = c^2,其中 c 是一个正整数。
因此,总共有 c 的个数满足条件,即总共有 sqrt(y/x) 个满足条件的 (p,q) 组合。
阅读全文