3045 Lcm与Gcd构造
已知:
gcd(a,b) = n
lcm(a,b) = m
求min(a,b)是多少
通过gcd的了解我们可以知道,两个数a == k1 * n以及b == k2 * n并且gcd(k1,k2) == 1
ab == n * m
m == a * b/n
ab == k1 * k2 * n * n
于是可以得到 m == k1 * k2 * n
将n除到左边,可以得出m/n == k1 * k2
于是k1 和 k2 都是 m / n的因子
这样就可以以根号的复杂度找出这两个因子,并判断k1 和 k2 是否是互质的
a + b == (k1 + k2 ) * n
所以说代码: