Problem:


Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

1 \leq N \leq 2 \times 10^5

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Accepted

Solution code:
import math
n, p = map(int, input().split())
s = input()

def nCr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
    #     print(tmp)
    #     ans += dp[tmp]
    #     dp[tmp] += 1
    # print(dp)

    # ベースの考え方。https://drken1215.hatenablog.com/entry/2020/03/08/020200
    # 素数pで割ったあまりは、0, 1, 2, ... p - 1になる。
    # 例えば、s=152467, p=3とする
    # 0 mod 3 = 0 (単独でも1つになるので、便宜上加える)
    # 7 mod 3 = 1
    # 67 mod 3 = 1
    # 467 mod 3 = 2
    # 2467 mod 3 = 1
    # 52467 mod 3 = 0
    # 152467 mod 3 = 1
    # となる。
    # 例えば、x mod 3 = 1について、考える。これは、7, 67, 2467, 152467の4つある。
    # これから、67 - 7 = 60で、3で割り切れる。2467 - 7 = 2560で、3で割り切れる。
    # このように、4つのうち2つを組み合わせれば、あまりの数が同じなので、p(3)で割り切れる組み合わせ
    # を作ることができる。
    # 467 mod 3 = 2については、あまりが2はコレしかないので、組み合わせることはできず、0となる。
    # また、あまりが2のものと、あまりが1のもの2個で組み合わせることはできない。なぜなら、
    # 467-67-7で組み合わせたところで、67と7が互いに相殺してしまうし、結果も393という、sの中に存在しない文字になるからである。
    # 基本はこれであり、下記のようになるが、これでは遅い（調べたところ、(int(s[i:])) % pが）。
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i:])) % p
    #     dp[tmp] += 1
    # for i in dp:
    #     ans += nCr(i, 2)
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
        dp[tmp] += 1
    for i in dp:
        ans += nCr(i, 2)
print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

div = [0 for _ in range(p)]

su = 0
for i in range(n):
	su = (su + s[i] * pow(10, i, p)) % p
	div[su] += 1

cnt = 0
if p in [2, 5]:
	if p == 2:
		ok = [0, 2, 4, 6, 8]
	else:
		ok = [0, 5]

	for i in range(len(s)):
		if s[i] in ok:
			cnt += n - i

else:
	for i in range(len(div)):
		x = div[i]
		if i == 0:
			y = x * (x + 1) // 2
		else:
			y = x * (x - 1) // 2
		cnt += y

print(cnt)

Submission status: Accepted

Solution code:
from copy import copy
from collections import defaultdict
n, p = map(int, input().split())

s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
        # tmp = (int(s[i]) * 10 ** (n - i - 1) + tmp) % p
        # print(tmp, int(s[i]) * 10 ** (n - i - 1))
        ans += dp[tmp]
        dp[tmp] += 1 
    # print(dp)

print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = input()
sum_count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            sum_count += (right + 1)
else:
    modp_count = [0] * p
    modp_count[0] = 1
    subs_modp, pow = 0, 1
    for si in s[::-1]:
        subs_modp += ((int(si)*pow) % p)
        subs_modp %= p
        modp_count[subs_modp] += 1
        pow = (pow*10) % p
        
    for count in modp_count:
        sum_count += count*(count - 1) // 2
print(sum_count)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()

ans = 0
if P == 2 or P == 5 :
    for i in range(N) :
        if int(S[i])%P == 0 :
            ans += i+1
    print(ans)
    exit()

modP = [0 for _ in range(P)]
modP[0] = 1
now = 0
t = 1
for i in range(N) :
    now += int(S[-1-i]) * t
    now %= P
    modP[now] += 1
    t = t * 10 % P

for r in modP :
    ans += r*(r-1)//2

print(ans)

Submission status: Accepted

Solution code:

n, p = map(int, input().split())
s = list(map(int, list(input())))


cnt = [0] * p
cnt[0] = 1
rem = 0
sum = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            sum += i + 1

else:
    for i in range(n):
        rem = (int(s[-i - 1]) * pow(10, i, p) + rem) % p
        sum += cnt[rem]
        cnt[rem] += 1

print(sum)

Submission status: Accepted

Solution code:
import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read

n, p = [int(i) for i in readline().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i, c in enumerate(s):
        if int(c) % p == 0:
            ans += i + 1
    print(ans)
    exit()


res = [0] * p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i * t
    now %= p
    res[now] += 1
    t = t * 10 % p
    


ans = 0
for i in res:
    ans += i * (i - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


n, p = map(int, input().split())
s = input()

if p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i + 1
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    # print(mod_list)
    # print(mod_dict)

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        res = 0

        for i in range(N):
            if int(S[i]) % P == 0:
                res += i + 1
        
        print(res)

    else:
        res = 0
        count = [0] * P
        r = 0

        for i in range(N-1, -1, -1):
            r = (int(S[i]) * pow(10, N-1 - i, P) + r) % P
            if r == 0: res += 1
            res += count[r]
            count[r] += 1
        
        print(res)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read

n, p = [int(i) for i in readline().split()]
s = input()

if p == 2 or p == 5:
    ans = 0
    for i, c in enumerate(s):
        if int(c) % p == 0:
            ans += i + 1
    print(ans)
    exit()

res = [0] * p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i * t
    now %= p
    res[now] += 1
    t = t * 10 % p

ans = 0
for i in res:
    ans += i * (i - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
N, P=map(int,input().split())
S = list(map(int,list(input())))

def ma25():
  ret = 0
  for i in range(N):
    if S[i]%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  dp[0] = 1
  r = 0
  for i in range(N-1,-1,-1):
    r = ((S[i]*pow(10,N-1-i,P))+r)%P
    dp[r] += 1
  ret = 0
  for m in dp:
    ret += m*(m-1)//2
  print(ret)

if P == 2 or P == 5:
  ma25()
else:
  ma()

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = list(map(int, list(input())))

if p in [2, 5]:
    ans = 0
    for i, x in enumerate(s):
        if x % p == 0:
            ans += i + 1
    print(ans)
    exit()

x = [0] * p
x[0] = 1
temp = 0
d = 1
for i in range(n-1, -1, -1):
    temp = (temp + s[i] * d) % p
    x[temp] += 1
    d = (d * 10) % p

ans = 0

for z in x:
    ans += z * (z-1) // 2

print(ans)

Submission status: Accepted

Solution code:
n,p = map(int, input().split())
s = input()
ans = 0
ruisekiwa = [0]*(n+1)
ten = 1

if 10 % p == 0:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(0, n)[::-1]:
        a =  int(s[i]) * ten % p
        ruisekiwa[i] = (ruisekiwa[i+1] + a) % p
        ten *= 10
        ten %= p

    cnt = [0]*p
    for i in range(0, n+1)[::-1]:
        ans += cnt[ruisekiwa[i]]
        cnt[ruisekiwa[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = defaultdict(int)
  a = int(s)
  r[a%p]+=1
  for i in range(n):
    a = (a%p-int(s[i])%p*pow(10,(n-1-i),p))%p
    r[a]+=1
  #print(r)
  ans = 0
  cnt=1
  for i in r.values():
    ans+=i*(i-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a =[]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])%p*pow(10,i,p))%p)
  a = [0]+a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())

s = input()

ruisekiwa = [0 for _ in range(0, n + 1)]
if 10 % p == 0:
    ans = 0
    for i in range(0, n):
        if (ord(s[i]) - ord('0')) % p == 0:
            ans += i + 1
    print(ans)
    exit()

ten = 1
for _i in range(0, n):
    i = n - _i - 1
    ruisekiwa[n - i] = ((ord(s[i]) - ord('0')) * ten + ruisekiwa[n - i - 1]) % p
    ten *= 10
    ten %= p

ans = 0
cnt = [0 for _ in range(0, p)]
for i in range(0, n+1):
    ans += cnt[ruisekiwa[i]]
    cnt[ruisekiwa[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = [int(x) for x in input()]
if P == 2:
    ans = 0
    for i in range(N):
        if S[N-1-i] % 2 == 0:
            ans += N-i
elif P == 5:
    ans = 0
    for i in range(N):
        if S[N-1-i] % 5 == 0:
            ans += N-i
else:
    ans = 0
    cnt = [0] * P
    cnt[0] = 1
    dec_mod, pre_mod = 1, 0
    for i in range(N):
        mod = (S[N-1-i] * dec_mod + pre_mod) % P
        ans += cnt[mod]
        cnt[mod] += 1
        dec_mod = dec_mod * 10 % P
        pre_mod = mod
print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
S=str(input())
ans=0

if 10%P==0:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
else:
    rem = [0]*P
    mod = 0
    ten = 1
    rem[mod]=1
    for i in range(N):
        mod=(mod+int(S[N-i-1])*ten)%P
        ten=ten*10%P
        rem[mod]+=1
    for j in rem:
        ans+=(j*(j-1))//2
print(ans)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  #pre = MS(i,int(s),pre)
  pre = pre + int(s)*i
  pre = pre%p
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  #pre = MS(i,int(s),pre)
  pre += int(s)*i
  pre %= p
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  pre = (int(s)*i+pre)
  return pre%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  pre += int(s)*i
  return pre%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
N, P = [int(x) for x in input().split()]
S = input()

res = 0

if P in [2,5]:
    for i in range(N):
        if int(S[i])% P == 0:
            res += i+1
else:
    dic = {0:1}
    t1 = 0
    t2 = 1
    for i in range(N):
        t2 = (10*t2) % P
        t1 = (int(S[N-1-i])*t2 + t1) % P
        if t1 in dic:
            res += dic[t1]
            dic[t1] += 1
        else:
            dic[t1] = 1

print(res)

Submission status: Accepted

Solution code:
# import time

N,P = list(map(int,input().split()))
S = input()

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    U.append(10001)
    # print(U)
    
    # t3 = time.time()
    
    c = 0
    
    """
    for i in range(P):
        m = U.count(i)
        c += m*(m-1)//2
    print(c)
    """
    U.sort()
    # print(U)
    idx = 0
    q = -1
    for i in range(N+2):
        if q != U[i]:
            q = U[i]
            m = i - idx
            idx = i
            c += m*(m-1)//2
    print(c)
    # t4 = time.time()
    # print(t4-t3)
    
    # 10032

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = list(map(int, input()))
if p == 2 or p == 5:
    ans = 0
    for i, digit in enumerate(s):
        if digit % p == 0:
            ans += i + 1
    print(ans)
else:
    ans = 0
    ten_pow_i_mod = 1
    #rev_s_mod = []
    temp_mod = 0
    mod_multiset = [1] + [0] * (p - 1)
    for digit in reversed(s):
        temp_mod += digit * ten_pow_i_mod
        temp_mod %= p
        #rev_s_mod.append(temp_mod)
        ans += mod_multiset[temp_mod]
        mod_multiset[temp_mod] += 1
        ten_pow_i_mod *= 10
        ten_pow_i_mod %= p
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, p = map(int, input().split())
s = input()

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + i + 1
    print(ret)
else:
    c_list = [0] * n
    power = 1
    for i in range(len(s)):
        c_list[i] = (c_list[i-1] + (int(s[-i-1]) * power)) % p
        power *= 10
        power = power % p
    c_list.append(0)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)

Submission status: Accepted

Solution code:
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split());S,a,i,j,c=input(),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i,j=(i+int(v)*j)%P,j*10%P;a+=c[i];c[i]+=1
else:
	for v in S:
		i+=1
		if int(v)%P<1:a+=i
print(a)

Submission status: Accepted

Solution code:
N,P=map(int,input().split());S,a,i,j,c=list(map(int,input())),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i,j=(i+v*j)%P,j*10%P;a+=c[i];c[i]+=1
else:
	for i,v in enumerate(S):
		if v%P<1:a+=i+1
print(a)

Submission status: Accepted

Solution code:
N,P=map(int,input().split());S,a,i,j,c=list(map(int,input())),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i=(i+v*j)%P;j=j*10%P;a+=c[i];c[i]+=1
else:
	for i,v in enumerate(S):
		if v%P<1:a+=i+1
print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

N, P = map(int, input().split())
S = input()[:-1]

if P in [2, 5]:
    ans = 0
    
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
        
    print(ans)
    exit()

cnt = defaultdict(int)
cnt[0] = 1
ans = 0
now = 0

for i in range(N-1, -1, -1):
    now += pow(10, N-1-i, P)*int(S[i])
    now %= P
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

N, P = map(int, input().split())
S = list(map(int, input()))

if P == 2:
    print(sum(i + 1 for i in range(N) if S[i] % 2 == 0))
elif P == 5:
    print(sum(i + 1 for i in range(N) if S[i] % 5 == 0))
else:
    x = [None] * (N + 1)
    x[N] = 0
    tmp = 1
    for i in reversed(range(N)):
        x[i] = (x[i + 1] + S[i] * tmp) % P
        tmp = tmp * 10 % P
    print(sum(i * (i - 1) // 2 for i in Counter(x).values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解法メモ]
各桁(桁数iとする)を10**i mod pの形で持っておく.
それの累積和をとって, 再びmod pをとると, 同じ数のペアの範囲はpの倍数になっていることが分かる.(他の問題でもこの解法あった気がする)
よって, 答えは同じ数のペアの数をすべて足したもの.

pが2や5の場合, *10が付くと必ず割り切れるので注意.
つまり, 1桁目が割り切れたら必ず割り切れる.⇒各桁を見ていってpで割り切れるならそれ以前の数を足せば良い.
(例)p=5, s=100のとき
    1は割り切れないからx
    0は割り切れるからo ⇒ 2桁目なので+2(10,0の場合)
    0は割り切れるからo ⇒ 3桁目なので+3(100,00,0の場合)
    ⇒答えは5
"""

n, p = LI() 
s = list(map(int,list(input())))
t = []
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    print(ans)
    quit()
 
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, p = LI() 
s = list(map(int,list(input())))
t = []
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    print(ans)
    quit()
 
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, p = map(int,input().split())
s = input()

res = 0

if p not in [2,5]:
    crem = 0
    
    crem_10 = [1]
    for i in range(1,n):
        crem_10 += [(crem_10[-1] * (10%p)) % p]
        
    dic_p = defaultdict(lambda : 0)
    for i,subs in enumerate(s[::-1]):
        crem += (int(subs) % p * crem_10[i]) % p
        crem %= p

        if crem == 0:
            res += 1
        res += dic_p[crem]

        dic_p[crem] += 1
        
else:
    for i,subs in enumerate(s[::-1]):
        if int(subs) % p == 0:
            res += n - i
    
print(res)

Submission status: Accepted

Solution code:
class Solution:

    def solve(self, N: int, P: int, S: str):

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  # int(S[i,N] mod P
            U[0] += 1

            num = 0
            base10_mod_p = 1
            for i in range(N):
                num = (num + int(S[N-i-1]) * base10_mod_p) % P
                base10_mod_p = (base10_mod_p * 10) % P

                U[num] += 1

            for u in U:
                answer += u * (u-1) // 2

        return answer


if __name__ == '__main__':

    # standard input
    N, P = map(int, input().split())
    S = input()

    # solve
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)

Submission status: Accepted

Solution code:
from sys import stdin 
from collections import defaultdict, Counter


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()

ans = 0 


# 2 cases
if P == 2 or P == 5:
	digitdiv = []
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1

else:
	#
	count = Counter()
	prefix = []
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1])*ten + mod) % P 
		prefix.append(x)
		count[x] += 1
		ten = (ten * 10) % P 
		mod = x
	prefix.append(0)
	count[0] += 1
	for val in count.values():
		ans += val*(val - 1)//2


print (ans)

Submission status: Accepted

Solution code:
n, p = (int(i) for i in input().split());

s = input();

if p == 2 or p == 5:
    res = 0;
    for i in range(len(s)):
        if int(s[i]) % p == 0:
            res += i + 1;
    print(res);
    exit(0);

h = [0 for i in range(len(s) + 1)];
st = 1;

for i in range(len(s) - 1,-1,-1):
    #print(i);
    h[i] = (st * int(s[i]) + h[i + 1]) % p;
    st = (st * 10) % p;

#print(h);

h.sort();

#print(h);

i = 0;
res = 0;

while i <= n:
    j = i;
    while j + 1 <= n and h[i] == h[j + 1]:
        j += 1;
    l = j - i + 1;
    res += (l * (l - 1)) // 2;
    i = j + 1;

print(res);

Submission status: Accepted

Solution code:
def main():
    n, mod = map(int, input().split())
    s = input().rstrip()
    a = [int(c)%mod for c in s]
    ans = 0
    if mod == 2 or mod == 5:
        for i in range(n):
            if a[i] == 0:
                ans += i + 1
    else:
        mul = 10 % mod
        for i in reversed(range(n-1)):
            a[i] = (a[i]*mul + a[i+1]) % mod
            mul = mul*10 % mod
        b = [0] * mod
        b[0] = 1
        for i in reversed(range(n)):
            ans += b[a[i]]
            b[a[i]] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  a=1
  for i in range(n)[::-1]:
     t+=int(s[i])*a
     t%=p
     a*=10
     a%=p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)