The problem was to find two numbers, a and b
, such that their greatest common divisor and their least common multiple would add up to a given number, x
. Moreover, the difference between the two numbers should be as small as possible, and a
must be less than or equal to b
X is between 2 and 1e9
.
its not full solution but maybe it can be useful
if i understand "add up" is a sum
so ok let gcd(a,b)=k
a=(p*k)
b=(t*k)
so lcm(a,b)=p*t*k
lcm(a,b)+gcd(a,b)= p*t*k+k = (p*t+1)(k)
every number has maximum 2*sqrt of divisors
so let check every divisors of x as (k)
By add up I mean, gcd(a,b)+lcm(a,b)=x
fixed
This problem is very similar to This Problem
We know that $$$n$$$ must be divisible by $$$gcd(a, b)$$$.
For every divisor $$$g$$$ of $$$n$$$, we will try to find pair $$$(a, b)$$$ with the minimum difference such that their gcd is $$$g$$$ and $$$gcd(a, b)$$$ + $$$lcm(a, b)$$$ = $$$n$$$.
we know that $$$a$$$ equals to $$$xg$$$ for some integer $$$x$$$ and $$$b$$$ is equal to $$$yg$$$ for some integer $$$y$$$.
$$$g + \frac{xg * yg}{g} = n$$$.
$$$g + xyg = n$$$.
$$$g(1 + xy) = n$$$.
$$$1 + xy = \frac{n}{g}$$$.
$$$xy = \frac{n}{g} - 1$$$.
now we need to find pair $$$(x, y)$$$ with the minimum difference such that their multiplication equals to $$$\frac{n}{g} - 1$$$ and $$$x$$$ and $$$y$$$ are coprime. We can simply iterate over the pairs of divisors of $$$\frac{n}{g} - 1$$$, check if they're coprime, and pick the one with the smallest difference. after that we know that pair $$$(xg, yg)$$$ is a valid answer.
Since we solved for every possible gcd of a valid pair, the answer is the pair with the minimum difference. Notice that the approximate upper bound for the number of divisors of $$$n$$$ is $$$n^\frac{1}{3}$$$, so this solution works in less than one second.