一、題目描述

P8712 [藍橋杯 2020 省 B1] 整數拼接

二、題目簡析

我們選兩個數 $a$ 和 $b$，用 $f(a,b)$ 表示 $a$ 在前、$b$ 在后的拼接，即 $f(a,b)=a?10^{b.size}+b$。要滿足 $k|f(a,b)$，則

$$\begin{array}{rl}f(a,b)& \equiv 0(\text{mod}k)\\ a?10^{b.size}+b& \equiv 0(\text{mod}k)\\ a?10^{b.size}& \equiv ?b(\text{mod}k)\end{array}$$

---

三、AC代碼

#include <bits/stdc++.h>using namespace std;const int MAX = 1e5 + 3;
typedef long long ll;
typedef pair<ll, int> P;P A[MAX];
int n, k, R[13][MAX], fact[13];
ll ans; P quickin(void)
{ll ret = 0;int cnt = 0;bool flag = false;char ch = getchar();while (ch < '0' || ch > '9'){if (flag == '-')    flag = false;ch = getchar();}while ('0' <= ch && ch <= '9' && ch != EOF){cnt++;ret = ret * 10 + ch - '0';ch = getchar();}if (flag)    ret = -ret;return P(ret, cnt);
}ll quickme(ll x, ll n, ll m)
{ll ret = 0;while (n > 0){if (n & 1)    ret = ret * x % m;x = x * x % m;n >>= 1;	}return ret;
}int main()
{#ifdef LOCALfreopen("test.in", "r", stdin);#endifcin >> n >> k;for (int i = 0; i < n; i++){A[i] = quickin();// 預處理 -b mod k int res = (-A[i].first) % k;if (res < 0)    res += k;R[A[i].second][res]++;}fact[1] = 10 % k;for (int i = 2; i <= 10; i++)fact[i] = fact[i - 1] * 10 % k;for (int i = 0; i < n; i++){int t = (-A[i].first) % k;if (t < 0)    t += k;for (int j = 1; j <= 10; j++){// 求 a * 10^b.size mod k int L = A[i].first * fact[j] % k;// 判重 if (A[i].second == j && t == L)ans += R[j][L] - 1;elseans += R[j][L];}}cout << ans << endl;return 0;	
}

---

完