算法
(思维) $O(n)$
记 $f(i)$ 表示 $S[i \cdots n]$ 所表示的十进制数
那么 $\frac{f(l) - f(r+1)}{10^{r+1-l}}$ 就是 $S[l \cdots r]$ 所表示的十进制数
当 $P = 2$ 或 $5$ 时,$10$ 不存在逆元,需要特殊处理:
- 对于每个子串,只需考虑其末尾的数能否被 $P$ 整除
对于其他情况:
$\frac{f(l) - f(r+1)}{10^{r+1-l}} \equiv 0 \pmod P \Leftrightarrow f(l)-f(r+1) \equiv 0 \pmod P \Leftrightarrow f(l) \equiv f(r+1) \pmod P$
所以我们只需先预处理出 $f(i)\% P$ 的值,记为 $g(i)$
然后倒序扫描 $S$ 中每个数,对于当前 $g(i)$ 对答案的贡献就是 $[i+1, n]$ 中满足 $g(j) = g(i)$ 的 $j$ 的个数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::string;
using std::vector;
using ll = long long;
int main() {
int n, p;
cin >> n >> p;
string s;
cin >> s;
if (10%p == 0) { // 2, 5
ll ans = 0;
rep(r, n) {
if ((s[r]-'0') % p == 0) {
ans += r+1;
}
}
cout << ans << '\n';
return 0;
}
vector<int> d(n+1);
int ten = 1;
for (int i = n-1; i >= 0; --i) {
int a = (s[i]-'0') * ten % p; // ten=10^((n-1)-i)
d[i] = (d[i+1]+a) % p;
ten *= 10; ten %= p;
}
ll ans = 0;
vector<int> cnt(p);
for (int i = n; i >= 0; --i) {
ans += cnt[d[i]];
cnt[d[i]]++;
}
cout << ans << '\n';
return 0;
}