Codeforces Solution-D. Concatenated Multiples-Solution in C, C++, Java, Python

Algorithm

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 $12$ and $3456$ is a number $123456$ .

Count the number of ordered pairs of positions $(i, j)$ ( $i \neq j$ ) in array $a$ such that the concatenation of $a_{i}$ and $a_{j}$ is divisible by $k$ .

Input

The first line contains two integers $n$ and $k$ ( $1 \leq n \leq 2 \cdot 10^{5}$ , $2 \leq k \leq 10^{9}$ ).

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Output

Print a single integer — the number of ordered pairs of positions $(i, j)$ ( $i \neq j$ ) in array $a$ such that the concatenation of $a_{i}$ and $a_{j}$ is divisible by $k$ .

Examples
input
Copy
6 11
45 1 10 12 11 7
output
Copy
7
input
Copy
4 2
2 78 4 10
output
Copy
12
input
Copy
5 2
3 7 19 3 3
output
Copy
0

Note

In the first example pairs $(1, 2)$ , $(1, 3)$ , $(2, 3)$ , $(3, 1)$ , $(3, 4)$ , $(4, 2)$ , $(4, 3)$ suffice. They produce numbers $451$ , $4510$ , $110$ , $1045$ , $1012$ , $121$ , $1210$ , respectively, each of them is divisible by $11$ .

In the second example all $n (n - 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 & Try With Live Editor

Input

–

cmd

6 11
45 1 10 12 11 7

Output

–

cmd

Demonstration

Codeforces Solution-D. Concatenated Multiples-Solution in C, C++, Java, Python ,Concatenated Multiples,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 3 years ago 876 0