You are given a sequence a0a1...aN−1 of digits and a prime number Q. For each i ≤ j with
ai ≠ 0, the subsequence aiai+1...aj 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, j) such that the corresponding subsequence is a multiple of Q.
The input consists of at most 50 datasets. Each dataset is represented by a line containing four
integers N, S, W, and Q, separated by spaces, where 1 ≤ N ≤ 105
, 1 ≤ S ≤ 109
, 1 ≤ W ≤ 109
,
and Q is a prime number less than 108
. The sequence a0...aN−1 of length N is generated by
the following code, in which ai
is written as a[i].
int g = S;
for(int i=0; i<N; i++) {
a[i] = (g/7) % 10;
if( g%2 == 0 ) { g = (g/2); }
else { g = (g/2) ^ W; }
}
Note: the operators /, %, and ^ 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.
The end of the input is indicated by a line containing four zeros separated by spaces.
For each dataset, output the answer in a line. You may assume that the answer is less than 230.
3 32 64 7 4 35 89 5 5 555 442 3 5 777 465 11 100000 666 701622763 65537 0 0 0 0
2 4 6 3 68530
In the first dataset, the sequence is 421. We can find two multiples of Q = 7, namely, 42 and
21.
In the second dataset, the sequence is 5052, from which we can find 5, 50, 505, and 5 being the
multiples of Q = 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.
In the third and fourth datasets, the sequences are 95073 and 12221, respectively.
Migrated from old NTUJ.
ACM ICPC 2010 Japan site
| No. | Testdata Range | Score |
|---|