Блог пользователя _MASTER__

Help in number theory problem
Автор _MASTER__, история, 21 месяц назад, По-английски 
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

.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
21 месяц назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This problem is very similar to This Problem

→ Ответить
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить