Given two coprime integers

We assume a<b. All integers in the form of

Moreover, becauce

*a*and*b*and another integer*n*, is it possible that*n=x*a+y*b*for some non-negative integers*x*and*y*?We assume a<b. All integers in the form of

*x*a+y*b*can be partitioned into*a*goups*G[i]={ x*a+y*b | (x*a+y*b)%a=i }*for*0<=i<a.*Furthermore, it’s obvoisly*G[i]={ lower[i], lower[i]+a, lower[i]+2*a,…}.*If r=n%a, we only need to check whether*n>=lower[r]*. We have*lower[r] = min{ y*b | y*b%a=r }*and it is can be calculated by the Euclid’s algorithm.Moreover, becauce

*(a-1)*b=max{ lower[i] | 0<=i<a }*, so*(a-1)*b-a*is the maximum integer which is not in the form of*x*a+y*b*.
Advertisements

## Leave a Reply