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)).