In this problem one should answer the query: how many beautiful numbers are there in the interval from 1 to R.

Clearly, to check whether a number is divisible by all its digits, it is sufficient to know the remainder of a division by the lcm of all possible digits (call this lcm M), that is M = 8 * 9 * 5 * 7 = 2520. The standart dynamic solution is supposed to maintain such state parameters: the length of the number, "strictly less" flag, current remainder of a division by M and the mask of already taken digits.

The first note: we can maitnain the lcm of the digits already taken, not the mask. This will decrease the number of different values of the last parameter (from 256 to 4 * 3 * 2 * 2 = 48, where 4 is the number of different powers of 2 etc).

Then, it is a good idea to pre-count transitions to the new parameters. But we wanted and tried to set such a time limit restriction, so that this solution would not be enough to avoid TL.

The idea that will decrease the running time even more lies in number theory. If we add digits from the end of a number we may see that the remainder of a number after division by 5 depends only on the last digit. Therefore, we may maintain the flag "last digit = 5 or 0" and ban transitions to the digit 5 if the flag is set to "false". Such an idea reduces the number of states by 5 * 2 / 2 = 5. This solution is fast enough to pass in any language, though there are even more powerful optimizations (the trick mentioned above can be done with digit 2 also).

it is actually a lot less due to unnecessity of re-initialization! thanks :)

In your last paragraph,you say: The idea that will decrease the running time even more lies in number theory. Dost it means "decrease time" is main in number theory,or it can "decrease time" base on number theory? I think it's the first meanning ,but my teammate is the second.⊙﹏⊙b