Well it is obvious that the greedy strategy of always taking the largest number you can will give the largest amount of unused tickets. Now implementing that strategy in O(K) is too slow. There might be some direct formula but in my solution I used simply binary search.

You can notice that the tickets you use will have values of {K, K-1, K-2 ... K-p, A}. That is, you'll use some amount of the largest consecutive tickets and then at most one other ticket. So you can binary search for p, that is binary search for the amount of largest consecutive tickets you'll take. Once you've fixed that it is easy to see whether you can get sum of N with at most one additional ticket. It is obvious that you are looking to minimize p so binary search works nicely with complexity of O(log K)