Just full search. ~O(sqrt(N)) in the worst case. To avoid TL before search do:
C = GCD(A,B);
A /= C;
B /= C;
N -= (N%C);
Think why you always can do this.
GOOD LUCK!