19284번 - Oneness 다국어

Define oneness of the number $x$ to be a number of integers $d > 1$ dividing $x$, whose decimal representation consists only of digit $1$. For example, $oneness(121) = 1$ and $oneness(1221) = 2$.

Number $n$ is obtained using the following algorithm involving a pseudo-random number generator. You are given two integers $l$ and $s_0$, which are the length of the decimal representation of $n$ and the generator seed.

The digits $d_0d_1 \ldots d_{l-1}$ of the number $n$ are generated by the following recursions:

$$ d_i = \left\lfloor s_i / 1024 \right\rfloor \mod 10 \\ s_{i + 1} = (747796405 s_i - 1403630843) \mod 2^{32} $$

It is guaranteed that $d_0$ is non-zero.

Calculate the total oneness over all integers between $1$ and $n$.

The first line contains two integers $l$, $s$ ($1\le l \le 250\,000$, $0 \leq s_0 < 2^{32}$), the number of digits in the decimal representation of $n$ and the seed of pseudo-random number generator that is used to create the decimal representation of $n$.

Output the sum of oneness over all integers between $1$ and $n$.

In sample tests $n$ equals 1, 11, 1221 and 9359 respectively.