Thanks for the hint!Sedefcho wrote:There is no mathematical formula. At least not till now
See this theorem. I think it can be used.
For even bases b the following can be proven:
If n ≥ b is a self number then n has the form n = (b-1) + a1(b^1+1) + a2(b^2+1) + ... with 0 ≤ ai < b.
Note that the reverse direction is not true.
Well, there is a mathematical formula. Let all the numbers generated by the formula that are not selfnumbers be called 'pseudo-selfnumbers'. If you list the pseudo-selfnumbers along with the coefficients a1, a2, ..., you will discover a regularity which will give an almost constant time algorithm to determine the rank of any selfnumber within the ordered set of all selfnumbers.
To the problemsetter:
Nice problem and a nice contest problemset!
Just one thing: I think it's better to avoid letting the input-format depend on the positions of line-breaks in the input-file. Even if you deliver a well formed input-file as problemsetter, you can never be sure what happens with it in the future; people may edit it, add or remove cases and then accidentally remove or add newlines. This happened on UVA on several occasions, leading to very hard to find bugs.
You could have avoided this, by adding a problem type indicator with every case, or writing it out explicitly:
Code: Select all
3 fun(101) fun(1,9) fun(20)