First of all. If you get WA#1, check how you scan input stream, cause they've put some trash in file.

I used the following idea. The whole number with base k divisible by ( k - 1 ), if sum( div( digit[ i ] ) ) is divisible by ( k - 1 ). Where digit[ i ] is k-based digit in input number ( char from input stream ); div( digit[ i ] ) is a remainder of division digit[ i ] * k by ( k - 1 ). Let see digit on i-th position, for example, it's A. So in decimal implementation it's equal to A * k ^ i.
A * k ^ i = A * k^i - A * k^(i-1) + A * k^(i-1) = A * k^(i-1) * ( k - 1 ) + A * k^(i-1)
A * k^(i-1) * ( k - 1 ) is divisible by ( k - 1 ), so we have to check only A * k^(i-1). If we repeat the same logic to this expression (i - 2) times, we see, that we have to check division A * k / ( k - 1 ).

I tried my best to explain the main idea, sorry if it can't be understood.