prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem F:</font> Find the Multiples</H1>3 4<p>5You are given a sequence <i>a</i><sub>0</sub><i>a</i><sub>1</sub>...<i>a</i><sub><i>N</i>-1</sub> digits and a prime number <i>Q</i>. For each <i>i</i> &le; <i>j</i> with <i>a<sub>i</sub></i> &ne; 0, the subsequence <i>a</i><sub><i>i</i></sub><i>a</i><sub></i>i</i>+1</sub>...<i>a<sub>j</sub></i> can be read as a decimal representation of a positive integer. Subsequences with leading zeros are not considered. Your task is to count the number of pairs (<i>i</i>, <i>j</i>) such that the corresponding subsequence is a multiple of <i>Q</i>.6</p>7 8<H2>Input</H2>9 10<p>11The input consists of at most 50 datasets. Each dataset is represented by a line containing four integers <i>N</i>, <i>S</i>, <i>W</i>, and <i>Q</i>, separated by spaces, where 1 &le; <i>N</i> &le; 10<sup>5</sup>, 1 &le; <i>S</i> &le; 10<sup>9</sup>, 1 &le; <i>W</i> &le; 10<sup>9</sup>, and <i>Q</i> is a prime number less than 10<sup>8</sup>. The sequence <i>a</i><sub>0</sub>...<i>a</i><sub><i>N</i>-1</sub> of length <i>N</i> is generated by the following code, in which ai is written as <span>a[i]</span>.12</p>13 14<pre>15    int g = S;16    for(int i=0; i&lt;N; i++) {17        a[i] = (g/7) % 10;18        if( g%2 == 0 ) { g = (g/2); }19        else           { g = (g/2) ^ W; }20    }21</pre>22 23<p>24<b>Note:</b> the operators <span>/</span>, <span>%</span>, and <span>^</span> are the integer division, the modulo, and the bitwise exclusiveor, respectively. The above code is meant to be a random number generator. The intended solution does not rely on the way how the sequence is generated. 25</p>26<p>27The end of the input is indicated by a line containing four zeros separated by spaces.28</p>29 30<H2>Output</H2>31 32<p>33For each dataset, output the answer in a line. You may assume that the answer is less than 2<sup>30</sup>.34</p>35 36<H2>Sample Input</H2>37<pre>383 32 64 7394 35 89 5405 555 442 3415 777 465 1142100000 666 701622763 65537430 0 0 044</pre>45 46<H2>Output for the Sample Input</H2>47<pre>482494506513526853053</pre>54 55<p>56In the first dataset, the sequence is 421. We can find two multiples of <i>Q</i> = 7, namely, 42 and 21.57</p>58 59<p>60In the second dataset, the sequence is 5052, from which we can find 5, 50, 505, and 5 being the multiples of <i>Q</i> = 5. Notice that we don't count 0 or 05 since they are not a valid representation of positive integers. Also notice that we count 5 twice, because it occurs twice in different positions.61</p>62 63<p>64In the third and fourth datasets, the sequences are 95073 and 12221, respectively.65</p>66 67 68