## Algorithm

D. Concatenated Multiples
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a, consisting of n positive integers.

Let's call a concatenation of numbers x and y the number that is obtained by writing down numbers x and y one right after another without changing the order. For example, a concatenation of numbers 1212 and 34563456 is a number 123456123456.

Count the number of ordered pairs of positions (i,j)(�,�) (ij�≠�) in array a such that the concatenation of ai�� and aj�� is divisible by k.

Input

The first line contains two integers n and k (1n21051≤�≤2⋅1052k1092≤�≤109).

The second line contains n integers a1,a2,,an�1,�2,…,�� (1ai1091≤��≤109).

Output

Print a single integer — the number of ordered pairs of positions (i,j)(�,�) (ij�≠�) in array a such that the concatenation of ai�� and aj�� is divisible by k.

Examples
input
Copy
6 1145 1 10 12 11 7
output
Copy
7
input
Copy
4 22 78 4 10
output
Copy
12
input
Copy
5 23 7 19 3 3
output
Copy
0
Note

In the first example pairs (1,2)(1,2)(1,3)(1,3)(2,3)(2,3)(3,1)(3,1)(3,4)(3,4)(4,2)(4,2)(4,3)(4,3) suffice. They produce numbers 45145145104510110110104510451012101212112112101210, respectively, each of them is divisible by 1111.

In the second example all n(n1)�(�−1) pairs suffice.

In the third example no pair is sufficient.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, k, a[N];
long long p[11];
vector<long long> rem[11];

int main() {
p[0] = 1;
for(int i = 1; i < 11; ++i)
p[i] = p[i - 1] * 10;

scanf("%d %d", &n, &k);
for(int i = 0; i < n; ++i)
scanf("%d", a + i);

for(int i = 0; i < n; ++i)
rem[int(floor(log10(a[i])) + 1)].push_back(a[i] % k);

for(int i = 1; i <= 10; ++i)
sort(rem[i].begin(), rem[i].end());

long long res = 0;
for(int i = 0, l, r; i < n; ++i) {
for(int j = 1; j <= 10; ++j) {
if(rem[j].empty())
continue;

long long tmp = (k - ((1ll * (a[i] % k) * (p[j] % k)) % k)) % k;
if(tmp < 0)
continue;

l = lower_bound(rem[j].begin(), rem[j].end(), tmp) - rem[j].begin();
r = upper_bound(rem[j].begin(), rem[j].end(), tmp) - rem[j].begin();

res += r - l;
}

if((1ll * ((a[i] % k) * (p[int(floor(log10(a[i])) + 1)] % k)) % k + a[i]) % k == 0)
--res;
}

printf("%lld\n", res);

return 0;
}
Copy The Code &

Input

cmd
6 11
45 1 10 12 11 7

Output

cmd
7