Atcoder Beginner Contest 164 D

题意： 给定一个只包含数字字符且不包含 $0$0字符的字符串 $S$S，问有子串组成的十位数是 $2019$2019的倍数。
数据范围： $\mid S\mid \le 2000000$∣S∣≤2000000
本题是 $AtcoderBeginnerContest158E$Atcoder Beginner Contest 158E的弱化版，故以 $158E$158E来证明。

题解：（参考题解）
对于一个数形如 $abcdefgh$abcdefgh设为 $AM$AM，另一个数形如 $efgh$efgh设为 $M$M， $p$p为 $10000$10000内的质数
若 $AM\%p==M\%p$AM%p==M%p即两者同余，可以得知 $A\times 10^{len\left(M\right)}\%p=0$A×10len(M)%p=0
证明即移项，根据取模的性质： $(a-b)\%p=(a\%p-b\%p)\%p$(a−b)%p=(a%p−b%p)%p，故得证。

下面来讨论符合的情况：
设 $B=10^{len\left(M\right)}$B=10len(M)，那么 $A\times B\%p=0$A×B%p=0则有：
$1.A\%p=0$1.A%p=0
$2.B\%p=0$2.B%p=0
$3.$3.由于模的性质，那么 $A\times B\%p=\left(\right(A\%p)\times (B\%p\left)\right)\%p=0$A×B%p=((A%p)×(B%p))%p=0，但是两个小于 $p$p的数的乘积是不会存在 $p$p这个质因子的，故该情况不符合，直接 $over$over

当第 $2$2种情况成立时，由于 $p$p是质因子， $10$10可分解为 $5$5与 $2$2的乘积，故任何符合条件的区间的个位必是 $5$5或 $2$2的倍数，即 $2,4,6,8,0,5$2,4,6,8,0,5

当第二种情况不成立即 p​=2&&p​=5，那么所有 $B\%p$B%p相等的情况互相可以组成一种。
即 $B1$B1和 $B2$B2的后缀模数相等时，如上的 $abcd$abcd部分是符合要求的区间。

代码：

$158E$158E

#include<iostream>
#include<cstdio>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
char s[N];
int cnt[10010];
int n, p;

int main()
{
	scanf("%d%d%s", &n, &p, s + 1);
	if(p == 2 || p == 5) {
		ll res = 0;
		for(int i = 1; i <= n; i++) {
			int v = s[i] - '0';
			if(v % p == 0) res += i;
		}
		
		return 0 * printf("%lld\n", res);
	}
	
	cnt[0] = 1;
	ll j = 1, now = 0, res = 0;
	for(int i = n; i >= 1; i--) {
		int v = s[i] - '0';
		now = (now + j * v) % p;
		res += cnt[now];
		cnt[now]++;
		j = j * 10 % p;
	}
	
	printf("%lld\n", res);
	
	return 0;
}

$164D$164D

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
const int p = 2019;
char s[N];
int cnt[2020];

int main()
{
	scanf("%s", s + 1);
	
	cnt[0] = 1;
	ll j = 1, now = 0, res = 0;
	for(int i = strlen(s + 1); i >= 1; i--) {
		int v = s[i] - '0';
		now = (now + j * v) % p;
		res += cnt[now];
		cnt[now]++;
		j = j * 10 % p;
	}
	
	printf("%lld\n", res);
	
	return 0;
}