## 【CodeForces-1029D】Concatenated Multiples

【CodeForces-1029D】Concatenated Multiples

Solution:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, k;
cin >> n >> k;
table[0] = 1;
for (int i = 1; i < LENGTH; i++)
table[i] = table[i - 1] * 10 % k;
for (int i = 0; i < n; i++) {
cin >> data[i];
LL tmp = data[i];
digits[i] = 0;
while (tmp) {
tmp /= 10, digits[i]++;
}
remain[digits[i]].push_back(data[i] % k);
}
for (int i = 0; i < LENGTH; i++)
sort(remain[i].begin(), remain[i].end());
LL ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < LENGTH; j++) {
LL rem = data[i] * table[j] % k;
vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
ans += r - l;
if (j == digits[i] && (rem ? k - rem : 0) == data[i] % k) ans--;
}
}
cout << ans << "\n";
return 0;
}

rem ? k – rem : 0这个写起来太麻烦了，按照题解的做法，可以改成：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, k;
cin >> n >> k;
table[0] = 1;
for (int i = 1; i < LENGTH; i++)
table[i] = table[i - 1] * 10 % k;
for (int i = 0; i < n; i++) {
cin >> data[i];
LL tmp = data[i];
digits[i] = 0;
while (tmp) {
tmp /= 10, digits[i]++;
}
remain[digits[i]].push_back(data[i] % k);
}
for (int i = 0; i < LENGTH; i++)
sort(remain[i].begin(), remain[i].end());
LL ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < LENGTH; j++) {
LL rem = data[i] * table[j] % k;
vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
ans += r - l;
if (j == digits[i] && (rem + data[i] % k) % k == 0) ans--;
}
}
cout << ans << "\n";
return 0;
}