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

Solution (Python):
def main():
  n,p=map(int,input().split())
  s=input()
  if 10%p==0:
    print(sum(i for i,x in enumerate(s,1) if int(x)%p==0))
    exit()
  s=s[::-1]
  x=[0]*p
  x[0]=1
  a,t=0,1
  for i in range(n):
    a=(a+int(s[i])*t)%p
    x[a]+=1
    t=(t*10)%p
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()

Solution (Python):
n,p=map(int,input().split())
s=input()
if 10%p==0:
  print(sum(i for i,x in enumerate(s,1) if int(x)%p==0))
  exit()
ans=0
u=0
d=1
l=[0]*p
l[0]=1
s=s[::-1]
for i in map(int,s):
  u=(u+i*d)%p
  l[u]+=1
  d=d*10%p
for i in l:
  ans+=i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter

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

def two_or_five():
    global S,N,P
    ans = 0
    for k,v in enumerate(S):
        v = int(v)
        if v % P:
            continue
        ans += k + 1
    return ans

def other():
    global S,N,P
    S = reversed(S)
    T = [0] * N
    a = 1
    for k,v in enumerate(S):
        T[k] = T[k-1] + a * int(v)
        T[k] %= P
        a *= 10
        a %= P
    T.append(0)
    ans = 0
    for k,v in Counter(T).items():
        ans += v * (v-1) // 2
    return ans

if P in {2,5}:
    print(two_or_five())
else:
    print(other())

Solution (Python):
import math
from functools import reduce
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,p = get_nums_l()
s = input()
X = list(map(int, list(s)))
n = len(s)

if p in (2,5):
    ans = 0
    for i,x in enumerate(X):
        if x%p == 0:
            ans += i+1
    print(ans)
else:
    ruiseki = [0] * (n+1)
    for i in (range(n-1, -1, -1)):
        ruiseki[i] = (X[i] * pow(10, (n-i-1), p) + ruiseki[i+1]) % p

    

    ans = 0
    count = defaultdict(int)

    for x in ruiseki:
        
        ans += count[x]
        count[x] += 1
    
    print(ans)

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

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



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

    ans = 0
    for c in cnt:
        ans += c * (c-1) // 2
    ans += cnt[0]
    print(ans)

Solution (Python):

import sys


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

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*int(S[i])
        a %= P
        U[i] = a
        beki = (beki * 10) % P
    table = [0]*P
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = int(next(tokens))  
    S = str(next(tokens))  
    solve(N, P, S)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        inv%=k
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)

Solution (Python):
from collections import defaultdict as dict

n, p = map(int, input().split())
s = input()
a = []
for x in s:
    a.append(int(x))

def solve():
    l = [0]*p
    ans = 0
    for x in a:
        l_ = [0] * p
        for i in range(p):
            l_[(i * 10 + x) % p] += l[i]
        l, l_ = l_, l
        l[x % p] += 1
        ans += l[0]

    print(ans)
if p <= 5:
    solve()
    exit()
x = 0
mem = dict(int)
mem[0] = 1
ans = 0
a.reverse()
d = 1
for y in a:
    x += d*y
    x %= p
    d = (d * 10) % p
    ans += mem[x]
    mem[x] += 1
    

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

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

print(ans)

Solution (Python):
n,p=map(int,input().split())
s=input()
ans=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
    print(ans)
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            ans+=i+1
    print(ans)
else:
    s=s[::-1]
    accum=[0]*n
    d=dict()
    for i in range(n):
        accum[i]=int(s[i])*pow(10,i,p)%p
    for i in range(n-1):
        accum[i+1]+=accum[i]
        accum[i+1]%=p
    accum[-1]%=p
    
    for i in range(n):
        if accum[i] not in d:
            if accum[i]==0:
                ans+=1
            d[accum[i]]=1
        else:
            if accum[i]==0:
              ans+=1
            ans+=d[accum[i]]
            d[accum[i]]+=1
    
    print(ans)

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




digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p

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

for i in remain:
	pcnt[i] += 1

if 10 % p == 0:
	ans = 0
	for i in range(n):
		if int(s[n-1-i]) % p == 0:
			ans += n - i
	print(ans)
else:
	ans = pcnt[0]
	for num in pcnt:
		if num != 0:
			ans += num * (num - 1) // 2

	print(ans)

Solution (Python):
import sys

from collections import Counter

def main():
    N,P = map(int,input().split())
    S = input()
    
    if 10%P == 0:
        ans = 0
        for i,st in enumerate(S[::-1]):
            num = int(st)
            if num % P == 0:
                ans += N-i
    else:
        ans,base = 0,1
        MOD_list = [0]
        for st in S[::-1]:
            num = int(st)
            MOD = (MOD_list[-1]+num*base)%P
            MOD_list.append(MOD)
            base *= 10
            base %= P
        c = Counter(MOD_list)
        for v in c.values():
            ans += (v*(v-1))//2
        
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

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

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

m = []
t = 1
q = 0
for i in range(N,0,-1):
    q = ((int(S[i-1]) % P) * t + q) % P
    m.append(q)
    t = (10 * t) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)

Solution (Python):


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





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


else:
    dp1 = [0] * (N+1)
    dp2 = [0] * (N+1)
    dp3 = [0] * P
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(int(sum))

Solution (Python):

import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()





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


else:
    dp1 = np.zeros(N + 1)
    dp2 = np.zeros(N + 1)
    dp3 = np.zeros(P)
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(int(sum))

Solution (Python):
from collections import defaultdict

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

ans = 0
if p == 2:
    for i in range(n):
        if s[i] % 2 == 0:
            ans += (i + 1)
elif p == 5:
    for i in range(n):
        if s[i] % 5 == 0:
            ans += (i + 1)
else:
    d = defaultdict(lambda: 0)
    ten = 1
    for i in reversed(range(n)):
        a = (s[i] * ten) % p
        d[i] = (d[i+1]+a) % p
        ten *= 10
        ten %= p

    cnt = defaultdict(lambda: 0)
    for i in reversed(range(n+1)):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)

mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, P = read_values()
    S = input().strip()

    if P in (2, 5):
        res = 0
        for i, s in enumerate(S):
            if int(s) % P == 0:
                res += i + 1
        print(res)

    else:
        r = 0
        D = {0: 1}
        res = 0
        d = 1
        for i, s in enumerate(S[::-1]):
            r += int(s) * d
            r %= P
            d *= 10
            d %= P
            c = D.setdefault(r, 0)
            res += c
            D[r] += 1
        print(res)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict

con = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))


def main():
	N, P = getlist()
	S = list(input())

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

	if P == 5:
		ans = 0
		for i in range(N):
			if int(S[i]) % 5 == 0:
				ans += i + 1
		print(ans)
		return
	
	
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var += pow(10, i, P) * int(S[N - 1 - i])
		var %= P
		D[var] += 1

	ans = 0
	for i in D:
		var = D[i]
		ans += int((var * (var - 1)) // 2)

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):


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

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

else:
    mm = {}
    r = 0
    mten = 1
    for i in range(n - 1, -1, -1):
        ch = int(s[i])
        r = (r + ch * mten) % p
        mten = (mten * 10) % p
        if r in mm:
            c += mm[r]
            mm[r] += 1
        else:
            mm[r] = 1

        if r == 0:
            c += 1
        
print(c)

Solution (Python):
n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
        
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

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

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)

Solution (Python):

def main():
    N, P = map(int, input().split())
    S = input()
    ans = 0
    mods = [0 for i in range(N+1)]
    digits = 1

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

    for i in range(N-1, -1, -1):
        mods[i] = (int(S[i]) * digits % P + mods[i+1]) % P
        digits = digits * 10 % P

    count = [0 for i in range(P)]
    for i in range(N, -1, -1):
        ans += count[mods[i]]
        count[mods[i]] += 1

    print(ans)

main()

Solution (Python):
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)

Solution (Python):
import collections

np_list = input().split(" ")
N = int(np_list[0])
P = int(np_list[1])

sum = 0
S = list(map(lambda s:int(s),input()[::-1]))



if P == 2 or P == 5:
    for i in range(0,N):
        if S[i]%P == 0:
            sum += N-i
else :
    digit = 1
    rem_list = [0]
    for i in range(N):
        rem_list.append(((S[i]*digit)%P+rem_list[i])%P)
        digit *= 10
        digit %= P
    c = collections.Counter(rem_list[1:])
    for i in range(1,N+1):
        if rem_list[i] == 0:
            sum += 1
        temp =c[rem_list[i]]
        temp -=1
        sum += temp
        c[rem_list[i]] = temp
print(sum)

Solution (Python):
n,p = list(map(int,input().split())); s = [int(i) for i in input()]

ans = 0

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

Solution (Python):
import sys



















readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, p = list(map(int, readline().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:
        c = [0] * p
        prev = 0
        c[0] = 1
        for i in range(n):
            num = int(s[n - i - 1])
            m = (num * pow(10, i, p) + prev) % p
            c[m] += 1
            prev = m

        for i in range(p):
            cnt = c[i]
            ans += cnt * (cnt - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, P = map(int, rl().split())
    S = input()
    
    ans = 0
    if P == 2 or P == 5:
        for i in range(N - 1, -1, -1):
            si = int(S[i])
            if si % P == 0:
                ans += i + 1
    else:
        cum = [0]
        t = 1
        for i in range(N - 1, -1, -1):
            cum.append(int(S[i]) * t % P)
            t = t * 10 % P
        for i in range(N):
            cum[i + 1] = (cum[i + 1] + cum[i]) % P
        
        counter = defaultdict(int)
        for val in cum:
            ans += counter[val]
            counter[val] += 1
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

N, P = MI()
S = input()

if P == 2:
    ans = 0
    for i, c in enumerate(S):
        if int(c) % 2 == 0:
            ans += i + 1
    print(ans)
elif P == 5:
    ans = 0
    for i, c in enumerate(S):
        if c in ['5', '0']:
            ans += i + 1
    print(ans)
else:
    d = defaultdict(int)
    tenmod = 1
    lastmod = 0
    for i, c in enumerate(reversed(S)):
        if i > 0:
            tenmod = tenmod * 10 % P
        lastmod = (int(c) * tenmod % P + lastmod) % P
        d[lastmod] += 1
    ans = 0
    for m, cnt in d.items():
        if m == 0:
            ans += cnt
        ans += cnt * (cnt - 1) // 2
    print(ans)

Solution (Python):
n, p = map(int, input().split())
s = input()[::-1]
if p == 2:
  ans = 0
  for num, i in enumerate(s):
    if int(i)%2 == 0:
      ans += n-num
elif p == 5:
  ans = 0
  for num, i in enumerate(s):
    if int(i)%5 == 0:
      ans += n-num
else:
  C = [0]*p
  now = 0
  for num, i in enumerate(s):
    a = int(i)
    now = (now+pow(10, num, p)*a)%p
    C[now] += 1
  ans = C[0]
  for c in C:
    ans += c*(c-1)//2
print(ans)

Solution (Python):
from collections import defaultdict

def main():
    N, P = map(int, input().split())
    S = list(map(int,list(input())))
    S_mod = [0] * N
    if P == 2:
        for i in range(N-1,-1,-1):
            if S[i] % 2 == 0:
                S_mod[i] = 1
        S_mod.reverse()
        ans = 0
        cnt = 0
        for i in range(N):
            if S_mod[i] == 1:
                cnt += 1
                ans += cnt
            else:
                ans += cnt
        print(ans)
        exit()
    if P == 5:
        for i in range(N-1,-1,-1):
            if S[i] % 5 == 0:
                S_mod[i] = 1
        S_mod.reverse()
        ans = 0
        cnt = 0
        for i in range(N):
            if S_mod[i] == 1:
                cnt += 1
                ans += cnt
            else:
                ans += cnt
        print(ans)
        exit()



    ten = 1
    for i in range(N-1,-1,-1):
        S_mod[i] = (S[i] * ten) % P
        ten *= 10
        ten %= P
    S_mod.reverse()
    S_acc = [0] * (N+1)
    for i in range(N):
        S_acc[i+1] = (S_acc[i] + S_mod[i]) % P
    d = defaultdict(int)
    for i in range(N+1):
        d[S_acc[i]] += 1
    ans = 0
    for i, j in d.items():
        if j >= 2:
            ans += (j * (j-1)) // 2

    print(ans)
    





if __name__ == "__main__":
    main()

Solution (Python):
n,p = [int(i) for i in input().split()]
s = input()
ans = 0
import collections

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

else:
  chk = []
  m = 0
  chk = collections.deque(chk)
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk.append(m)
  chk.append(0)
  chk = list(chk)
  c = collections.Counter(chk)
  for i in range(p):
    ans += c[i]*(c[i]-1)/2
  print(int(ans))

Solution (Python):
import sys
input = sys.stdin.readline
n,p = [int(i) for i in 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()

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += i*(i-1)/2
  print(int(ans))

Solution (Python):
import sys
input = sys.stdin.readline
n,p = [int(i) for i in 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()
    
else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  chk= [i*(i-1)/2 for i in chk]
  print(int(sum(chk)))

Solution (Python):
def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  import collections
 
  if p == 2 or p == 5:
      for i in range(n):
          if int(s[i]) % p == 0:
              ans += i + 1
      print(ans)
      exit()
 
  else:
    chk = []
    m = 0
    chk = collections.deque(chk)
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i,p)+m)%p
      chk.append(m)
    chk.append(0)
    chk = list(chk)
    c = collections.Counter(chk)
    for i in range(p):
      ans += c[i]*(c[i]-1)/2
    print(int(ans))
if __name__ == '__main__':
    main()

Solution (Python):
def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  
  import math
  def nCr(n, r):
    if n < r:
      return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

  else:
    chk = [0]*p
    chk[0] = 1
    m = 0
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i,p)+m)%p
      chk[m] += 1
    for i in chk:
      ans += nCr(i,2)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n,p = [int(i) for i in input().split()]
s = input()
ans = 0

import math
def nCr(n, r):
  if n < r:
    return 0
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

else:
  chk = [0]*p
  chk[0] = 1
  m = 0
  for i in range(n)[::-1]:
    m = (int(s[i])*pow(10,n-1-i,p)+m)%p
    chk[m] += 1
  for i in chk:
    ans += nCr(i,2)
  print(ans)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict

n, p = na()
s = ns()

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

c = [0] * (n + 1)
m = 1
for i in range(n - 1, -1, -1):
    t = int(s[i]) * m % p
    c[i] = (c[i + 1] + t) % p
    m *= 10
    m %= p

ans = 0
dic = defaultdict(int)
for i in range(n, -1, -1):
    ans += dic[c[i]]
    dic[c[i]] += 1

print(ans)

Solution (Python):
n, p = map(int, input().split())
s = list(map(int, input()))
ans = 0

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

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * p
for x in cum: t[x] += 1

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

Solution (Python):
from collections import defaultdict
N,p = map(int,input().split())
S = input()
S = S[::-1]
d = defaultdict(lambda:0)
r = 0
for i in range(N):
    r += int(S[i])*pow(10,i,p)
    r %= p
    d[r] += 1

ans = 0
for r in d:
    ans += d[r]*(d[r]-1)//2
ans += d[0]

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

print(ans)

Solution (Python):
def main():
    n,p = map(int,input().split())
    s = input()
    l = [0 for i in range(p)]
    l[0] = 1
    ten = 1
    cnt = 0

    ans = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p == 0:
                ans += i+1
    else:
        for i in range(n):
            cnt = (cnt + int(s[-i-1]) * ten) % p
            l[cnt] += 1
            ten = (ten * 10) % p
        for i in l:
            if i > 1:
                ans += i * (i - 1) // 2

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, P = (int(i) for i in input().split())
    S = input()
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S, start=1):
            if int(s) % P == 0:
                ans += i
        return print(ans)
    cnt = [0]*P
    cnt[0] += 1
    d = 1
    cur = 0
    for s in S[::-1]:
        s = int(s)
        cur += (s * d) % P
        cur %= P
        d *= 10
        d %= P
        cnt[cur] += 1
    for c in cnt:
        if c:
            ans += c*(c-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,p = map(int,input().split())
s = input()
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2

print(ans)

Solution (Python):
n,p=map(int,input().split())
s=list(map(int,list(input()[::-1])))
if p in [2,5]:
  ans=0
  for i in range(n):
    if s[-i-1]%p==0:ans+=i+1
  print(ans)
  exit()
from collections import defaultdict
d=defaultdict(int)
t=0
d[t]+=1
m=1
for i in range(n):
  t+=m*s[i]
  t%=p
  d[t]+=1
  m*=10
  m%=p
print(sum(d[i]*(d[i]-1)//2 for i in range(p)))

Solution (Python):
from collections import defaultdict

N, P = map(int, input().split())
S = input()
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        d = int(S[i])
        if d % P == 0:
            ans += i + 1
    print(ans)
else:
    ans = 0
    count = defaultdict(int)
    count[0] = 1
    num = 0
    factor = 1
    for i in range(N)[::-1]:
        num = (num + int(S[i]) * factor) % P
        factor = factor * 10 % P
        ans += count[num]
        count[num] += 1
    print(ans)

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

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

a = [0]
r = 1
for c in S[::-1]:
    d = int(c)
    a.append((a[-1] + d*r) % P)
    r *= 10
    r %= P
from collections import Counter
ctr = Counter(a)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

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

def smallSol():
    dp = [0] * P
    ans = 0
    for s in map(int, S):
        newDp = [0] * P
        newDp[s % P] += 1
        for p in range(P):
            newDp[(p * 10 + s) % P] += dp[p]
        dp = newDp
        ans += dp[0]
    return ans

def largeSol():
    cnt = [0] * P
    cnt[0] += 1
    ret = 0
    now = 0
    for i, s in enumerate(map(int, S[:: -1])):
        now = (pow(10, i, P) * s + now) % P
        ret += cnt[now - P]
        cnt[now] += 1
    return ret

print(smallSol() if N * P <= 10**6 else largeSol())

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

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

elif p == 5:
    for i, char in enumerate(s):
        if int(char) % 5 == 0:
            ans += i + 1
    print(ans)

else:
    a = [0] * (n + 1)
    for i in range(n):
        a[i + 1] = a[i] + int(s[n - i - 1]) * pow(10, i, p)
        a[i + 1] %= p
    memo = {}
    for i in range(n + 1):
        if a[i] not in memo:
            memo[a[i]] = 1
        else:
            memo[a[i]] += 1
    for i in memo:
        ans += memo[i]* (memo[i] - 1) // 2
    print(ans)

Solution (Python):
from collections import defaultdict

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

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)%P]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())

Solution (Python):
from collections import defaultdict
N,P=map(int,input().split())
S=input()

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

else:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*pow(10,i,P)
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)