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)).
I think that this problem can be solved next way:
Yes, you are right :)
This problem has me completely stuck.
Finally AC, thank you very much.