## Editorial for TLE '17 Contest 8 P3 - Curious Numbers

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

The is a red herring and should not add any additional difficulty to this problem.

For the first of the points, for every query, we check all numbers from to to see if they are palindromes and divisible by . An easy way to check if a number is a palindrome is to reverse the number using multiplication and mod by .

Time Complexity:

For the next of the points, we should first precompute whether or not each number from to is a palindrome divisible by . Note that there are only approximately palindromes in this range. Thus, for every query, we iterate through all of the palindromes and count those that are in between and and divisible by .

Time Complexity:

For full points, we generate all palindromes efficiently. Start with all one and two digit palindromes, including 0 and 00. Then, for each existing palindrome, add digits 0 through 9 to the front and end to create palindromes with two more digits. Repeat until palindromes of length have been generated. Finally, remove all palindromes that end with 0 (as they must begin with 0) or are not divisible by .

Next, we sort these palindromes, and we can answer the queries using binary search. Note that it is possible to generate palindromes in order, ridding the need to sort.

Time Complexity: