My approach divides into 2 cases

I) A>= sqrt(N) or B>=sqrt(N)
  this can be solved by brute force in O(sqrt(N))

II) A<sqrt(N) and B<sqrt(N)
  now this is more interesting
  in case of gcd(A,B)=1
  you can proof that there exist x,y>=0 that A*x+B*y = N
    since A*x congruent to N (mod B) -> x = N*inv(A,B) % B
    hence 0<=x<=B-1 but B<sqrt(N) and A<sqrt(N)
    then A*x < N so y >= 0
  in case of gcd(A,B)>1
    that's your work!

:)