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

Find minimum sum of A and B using given operations
Автор greedyman, 9 лет назад, По-английски

You have positive numbers A and B (1 <= A,B <= 10^18) and following operations:
  1) If P is prime number and divides A and B, then A/=P and B/=P.
  2) If P is prime number and divides A and P^2 divides B, then A/=P and B/=P^2.
Find minimum sum of A and B using operations 1 and 2 (no matter how many times).

Do you have any ideas?
It seems to have quite easy solution, and should work in something like O(lg max(A,B)).

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I think that this problem can be solved next way:

  1. g1 = gcd(A, B), B /= g1 — remove common prime divisors
  2. g2 = gcd(A, B), A /= g1, B /= g2 — remove common prime divisors, that were twice at B
  3. res = A + B
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, you are right :)
    This problem has me completely stuck.

    Finally AC, thank you very much.

    → Ответить