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():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()


def solve25():
    ans = 0
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
    return ans


if P in (2, 5):
    ans = solve25()
    print(ans)
    exit()


U = [0] * N
n = 0
p = 1
for i, c in reversed(list(enumerate(S))):
    n += int(c) * p
    n %= P
    U[i] = n
    p *= 10
    p %= P

counts = [0] * P
for u in U:
    counts[u] += 1

ans = counts[0]
for i in reversed(range(N)):
    
    counts[U[i]] -= 1
    ans += counts[U[i]]
print(ans)

Solution (Python):
from collections import Counter

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

c = 0

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

else:
    T = [0]*(N+1)
    d = 1
    for i,v in enumerate(S[::-1]):
        a = (int(v) * d + T[i])% P
        T[i+1] = a
        d *= 10
        d %= P
    count = Counter(T)

    c = sum(x * (x -1) / 2 for x in count.values())

print(int(c))

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

def twofive(n, p, s):
    res = 0
    for i in range(n):
        mostlow = int(s[i])
        if mostlow%p==0:
            res += i+1
    return res

def others(n, p, s):
    from collections import Counter
    res = 0
    
    num = 0
    amari = [0 for _ in range(n+1)]
    for i in range(n)[::-1]:
        j = n-1-i
        num += int(s[i]) * pow(10, j, p) %p
        num %= p
        amari[j+1] = num
    
    amaricnt = Counter(amari)
    for val in amaricnt.values():
        if val == 1:
            continue
        else:
            res += val*(val-1)//2
    
    return res

if p == 2 or p==5:
    print(twofive(n, p, s))
else:
    print(others(n, p, s))

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

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

else:
    cnt = [0] * p
    cnt[0] = 1
    now = 0
    for i, j in enumerate(reversed(s)):
        now = (int(j) * pow(10, i, p) + now) % p
        ans += cnt[now]
        cnt[now] += 1

print(ans)

Solution (Python):
N, P = 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)
    import sys
    sys.exit(0)

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

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

print(ans)

Solution (Python):
n,p=map(int,input().split())
if p==2 or p==5:
  print(sum(i+1 for i,x in enumerate(input()) if int(x)%p==0))
  exit()
t=1
y=0
c=[0]*p
for x in map(int,input()[::-1]):
  y+=t*x
  y%=p
  c[y]+=1
  t*=10
  t%=p
print(sum(i*(i-1)//2 for i in c)+c[0])

Solution (Python):
N, P = map(int, input().split())
S = list(map(int,list(input())))
U = [0 for i in range(N+1)]
POW = [1 for i in range(N)]

for i in range(N-1):
    POW[i+1] = (POW[i]*10) % P

for i in range(N):
    U[N-(i+1)] = (U[N-i] + S[N-1-i] * POW[i]) % P
    
def solve(U,S):
    if P == 2 or P == 5:
        return solve1(S)
    else:
        return solve2(U)
    
def solve1(S):
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    return ans

def solve2(U):
    ans = 0
    cnt = [0 for i in range(P)]
    for i in range(N+1):
        cnt[U[i]] += 1
    for i in range(P):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans

print(solve(U,S))

Solution (Python):
from itertools import accumulate
from collections import Counter

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

if P == 2 or P == 5:
    s_can = [1 if i % P == 0 else 0 for i in S]
    
    
    answer = sum(idx for idx, i in enumerate(s_can, 1) if i)
    print(answer)
else:
    s = [0]
    t = 1
    for i in S[::-1]:
        r = i % P
        s.append(r * t % P)
        t = t * 10 % P

    s_acc = [None] * (N + 1)
    tmp = 0
    for idx, i in enumerate(s):
        tmp = (tmp + i) % P
        s_acc[idx] = tmp

    c = Counter(s_acc)
    answer = sum(i * (i - 1) // 2 for i in c.values())
    print(answer)

Solution (Python):
N, P = [int(i) for i in input().strip().split(" ")]
S = [i for i in input()]

r = [int(i) % P for i in S]

ret = 0

if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            ret += (i+1)
else:
    from collections import defaultdict
    S.reverse()
    mp = defaultdict(int)
    mp[0] = 1
    cur = 0
    p10 = 1
    for c in S:
        cur = (cur + int(c) * p10) % P
        ret += mp[cur]
        mp[cur] += 1
        p10 *= 10
        p10 %= P

print(ret)

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

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

u = defaultdict(int)
u[0] = 1
f = 1
d = 0
for i in range(n-1,-1,-1):
    d = (d + int(s[i])*f)%p
    f = (f*10)%p
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)

Solution (Python):
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:
    tmp = 0
    d = defaultdict(int)
    d[0] = 1
    for i in range(n)[::-1]:
        tmp += int(s[i]) * pow(10, n - i - 1, p)
        tmp %= p
        ans += d[tmp]
        d[tmp] += 1
print(ans)

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

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

ans = 0
if P == 2:
    for i, s in enumerate(S, start=1):
        if int(s) % 2 == 0:
            ans += i
elif P == 5:
    for i, s in enumerate(S, start=1):
        if s in "05":
            ans += i
else:
    T = [0] * (N+1)
    d = 1
    for i, s in enumerate(S[::-1], start=1):
        s = int(s) * d + T[i - 1]
        T[i] = s % P
        d *= 10
        d %= P
    c = Counter(T)
    ans = sum(x * (x - 1) // 2 for x in c.values())

print(ans)

Solution (Python):
from collections import Counter

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

ans = 0
if 10 % p == 0: 
    for i, num in enumerate(s, 1):
        if num % p == 0:
            ans += i
    print(ans)
    exit()

s = s[::-1]
power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p







count = [0] * p
count[0] = 1
for i in t:
    ans += count[i]
    count[i] += 1
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    n, p = LI()
    s = S()
    ans = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p != 0:
                pass
            else:
                ans += i + 1
    else:
        tmp = 0
        d = defaultdict(int)
        d[0] = 1
        for i in range(n - 1, -1, -1):
            tmp += int(s[i]) * pow(10,n-i-1,p)
            tmp %= p
            ans += d[tmp]
            d[tmp] += 1
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import Counter

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

ans = 0
if 10 % p == 0: 
    for i, num in enumerate(s, 1):
        if num % p == 0:
            ans += i
    print(ans)
    exit()

s = s[::-1]
power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

counter = Counter(t)
for i in counter.values():
    ans += i * (i-1) // 2
ans += counter[0]
print(ans)

Solution (Python):
import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    mod = 0
    keta_mod = 1
    for i, _s in enumerate(s[::-1]):
        keta_mod = keta_mod * 10 % p
        mod = (keta_mod * int(_s) + mod) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)

Solution (Python):



from collections import Counter
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)
    exit()

num = 0
a = [0] * (n+1)
for i in reversed(range(n)):
    j = n-1 - i
    num += int(s[i]) * pow(10, j, p) % p
    num %= p
    a[j+1] = num

ctr = Counter(a)
ans = 0
for v in ctr.values():
    ans += v * (v-1) // 2

print(ans)

Solution (Python):
from collections import Counter

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

ans = 0

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

    for i in range(N):
        M.append(pow(10, i, P) * int(S[-1 - i]) % P)

    for i in range(N):
        cum.append((cum[-1] + M[i]) % P)

    C = Counter(cum)

    for v in C.values():
        ans += v * (v - 1) // 2

print(ans)

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

dp = [0] * (N+1)
digit = 1
if P in [2, 5]:
  count = 0
  for i, s in enumerate(S, 1):
    s = int(s)
    if s%P == 0:
      count += 1
    dp[i] = dp[i-1] + count
else:
  mod_count = dict(zip(range(P), [0]*P))
  pre_r = 0
  for i, s in enumerate(S, 1):
    s = int(s)
    r = (digit * s + pre_r) % P
    dp[i] = dp[i-1] + mod_count[r]
    if r == 0:
      dp[i] += 1
    mod_count[r] += 1
    pre_r = r
    digit = (digit * 10) % P

print(dp[-1])

Solution (Python):
from collections import Counter
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)
    exit()

num = 0
a = [0] * (n+1)
for i in reversed(range(n)):
    j = n-1 - i
    num += int(s[i]) * pow(10, j, p) % p
    num %= p
    a[j+1] = num

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()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    t, s = 0, 1
    for i in range(N-1, -1, -1):
        t = (int(S[i])*s+t)%P
        U[t] += 1
        s = s*10%P
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)

Solution (Python):
def e_divisible_substring():
    
    from collections import Counter
    N, P = [int(i) for i in input().split()]
    S = [int(ch) for ch in input()]  

    def solve_specific(S, p):
        """p -> 2 または 5 のときは、連続部分文字列が p の倍数かどうかは
        1の位だけ見ればよい。つまり左から k 番目に 2 か 5 の倍数がある場合、
        k 個の連続部分文字列が p の倍数となる。"""
        return sum(k for k, s in enumerate(S, 1) if s % p == 0)

    if P in (2, 5):
        return solve_specific(S, P)

    s = S[::-1]  
    
    u = [0] * N
    u[0] = s[0] % P
    power = 1
    for i in range(1, N):
        power *= 10
        power %= P  
        u[i] = u[i - 1] + power * s[i]
        u[i] %= P
    
    
    
    counter = Counter(u)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]

print(e_divisible_substring())

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,p = m()

s = input().split()[0]

co = 0

mo = [0 for i in range(p)]

data = [0 for i in range(n)]

po = [1 for i in range(n)]

for i in range(1,n):
    po[i] = (po[i-1] * 10) % p

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

else:
    s = s[::-1]
    data[0] = int(s[0]) % p
    for i in range(1,n):
        data[i] = (int(s[i]) * (po[i]) + data[i-1]) % p

    mo[0] = 1
    for i in range(n):
        co += mo[data[i]]
        mo[data[i]] += 1



print(co)

Solution (Python):
from collections import Counter

N, P = list(map(int, input().split()))
S = [int(c) for c in input().rstrip()]


if P in [2, 5]:
    total = 0
    for i, x in enumerate(S):
        if x % P == 0:
            
            
            
            
            total += i + 1
    print(total)
else:
    

    
    
    
    
    
    
    
    
    
    

    CHECK = False
    suf = [0]
    power = 1
    for x in reversed(S):
        suf.append(suf[-1] + x * power)
        power *= 10
        if not CHECK:
            
            suf[-1] %= P
            power %= P
    if CHECK:
        
        N = len(S)
        for i in range(N):
            for j in range(i + 1, N + 1):
                print(
                    i,
                    j,
                    int("".join(map(str, S[N - j : N - i]))) * (10 ** i),
                    suf[j] - suf[i],
                )
        print(suf)

    
    total = 0
    counts = Counter()
    for x in suf:
        x = x % P
        total += counts[x]
        counts[x] += 1
    print(total)

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

if 10%p==0:
    result = 0
    for i in range(n):
        if s[i]%p==0:
            result += n-i
else:
    r = [0 for _ in range(p)]
    r[0] = 1
    t = 0
    ten = 1
    for i in s:
        t = (t+i*ten)%p
        ten = (ten*10)%p
        r[t] += 1
    result = 0
    for i in r:
        result += i*(i-1)//2
print(result)

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

res = 0

if P == 2 or P == 5:
    
    for i in range(N):
        if int(S[N - i - 1]) % P == 0:
            res += N - i
else:
    val = [0] * P
    tenfactor = 1
    cur = 0
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * tenfactor) % P
        tenfactor = (tenfactor * 10) % P
        val[cur] += 1
        
    
    for p in range(P):
        res += val[p] * (val[p] - 1) // 2
    
print(res)

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

'''
N, P  = 10, 7
S = '1234567890'
tans = 0
for i in range(N):
    for j in range(i+1,N+1):
        t = int(S[i:j])
        tans += ((t % P) == 0)
print(tans)
'''

S = list(map(int,S))

ans = 0
if P == 2:
    for i,s in enumerate(S):
        if s % 2 == 0:
            ans += i + 1
elif P == 5:
    for i,s in enumerate(S):
        if s % 5 == 0:
            ans += i + 1
else:
    res = []
    n = 0
    k = 1
    for s in S[::-1]:
        n = (s * k + n) % P
        k = (k * 10) % P
        res.append(n)

    res.append(0) 
    
    

    cnts = Counter(res)
    for ind, cnt in cnts.items():
        if cnt == 1:
            continue
        ans += cnt * (cnt - 1) // 2

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, P, S):
    if P == 2 or P == 5:
        n = 0
        ans = 0
        for c in reversed(S):
            if int(c) % P == 0:
                n += 1
            ans += n
        return ans

    p = Counter()
    t = 1
    ans = 0
    c = 0
    for i in range(N):
        a = ((int(S[N-i-1]) * t) + c) % P
        c = a
        if a == 0:
            ans += 1
        ans += p[a]
        p[a] += 1
        t = (t * 10) % P

    return ans


def main():
    N, P = read_int_n()
    S = read_str()
    print(slv(N, P, S))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, P, S):
    if P == 2 or P == 5:
        n = 0
        ans = 0
        for c in reversed(S):
            if int(c) % P == 0:
                n += 1
            ans += n
        return ans

    p = Counter()
    t = 1
    ans = 0
    c = 0
    for i in range(N):
        a = ((int(S[N-i-1]) * t) + c)% P
        c = a
        if a == 0:
            ans += 1
        ans += p[a]
        p[a] += 1
        t = (t * 10) % P

    return ans

def main():
    N, P = read_int_n()
    S = read_str()
    print(slv(N, P, S))



if __name__ == '__main__':
    main()

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

m = [0 for i in range(p)]

ans = 0
m[0] = 1

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

else:
    cnt = 10 % p
    for i in range(n):
        s = int(S[n-1-i])
        if i == 0:
            r = s%p
        else:
            r = (cnt*s+r) % p
            cnt = cnt * 10 % p
        if m[r] >= 1:
            ans += m[r]
        m[r] += 1

print(ans)

Solution (Python):
N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    temp = 0
    power = 1
    for i in range(N):
        temp += pow(10, i, P) * int(S[N-i-1])
        temp %= P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

Solution (Python):
N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    temp = 0
    power = 1
    for i in range(N):
        power *= 10
        power %= P
        temp += power * int(S[N-i-1])
        temp %= P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

Solution (Python):
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=ans+i+1
  print(ans)
elif p==5:
  ans=0
  for i in range(n):
    if int(s[i])%5==0:
      ans=ans+i+1
  print(ans)
else:
  R=[0]*p
  x=0
  y=1
  for i in range(n-1,-1,-1):
    a=int(s[i])
    b=(a*y+x)%p
    R[b]=R[b]+1
    y=y*10%p
    x=b
  ans=R[0]*(R[0]+1)//2
  for i in range(1,p):
    ans=ans+(R[i]*(R[i]-1))//2
  print(ans)

Solution (Python):
N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    temp = 0
    power = 1
    for i in range(N):
        power *= 10
        power %= P
        temp += power * int(S[N-i-1])
        temp %= P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

Solution (Python):

n,p=map(int,input().split())
s=input()
ans=0
if p == 2:
    for i in range(n):
        if s[i] in ["0","2","4","6","8"]:
            ans+=i+1
elif p == 5:
    for i in range(n):
        if s[i] in ["0","5"]:
            ans+=i+1
else:
    mod=[1] + [0]*(p-1)
    a=0
    for i in range(n):
        si = int( s[n-1-i] )
        a = si*pow(10,i,p) + a 
        mod[ a%p ]+=1
    ans =  sum(m*(m-1)//2 for m in mod)
print(ans)

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

counter=0
def power_func(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    elif b%2==1:
        return (a*power_func(a,b-1,p ))%p
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    temp=0
    for i in range(N):
        M = power_func(10,N-i,P)
        temp=(int(S[i])*M+temp)%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)

Solution (Python):



import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128



def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	ans=0
	if p%2==0 or p%5==0:
		for i0 in range(len(s)-1,-1,-1):
			sub=int(s[i0:i0+1])
			if sub%p==0:
				ans+=i0+1
	else:
		numP0=np.zeros(p, int32)
		numP0[0]=1
		r=0
		modD=int(1%p)
		for i0 in range(len(s)-1,-1,-1):
			
			sub=s[i0:i0+1]
			sub=int(sub)
			sub=r+sub*modD
			r=sub%p
			ans+=numP0[r]
			numP0[r]+=1
			modD=int((modD*10)%p)
	print(ans)
		
	

if __name__=="__main__":
	inputs=getInputs()

	main(inputs)

Solution (Python):
"""

問題文:

制約:

解読:
- 2, 5はO(n)で求められるとのこと
  - 最後の桁がpで割り切れるかどうかのみで判定可能なため
  - solve1で、cntをi + 1でカウントしている理由:
    - 対象となる部分文字列は連続した部分文字列
    - iをインクリメントしながらカウント
    - i番目の数字を含む部分文字列のみカウントすればよい -> (i + 1)個
"""
n, p = map(int, input().split())
s = list(map(int, list(input())))
u = [0 for _ in range(n + 1)]

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


def solve(u, s, p):
    if 2 == p or 5 == p:
        return solve1(s, p)
    else:
        return solve2(u, p)


def solve1(s, p):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i + 1
    return ans


def solve2(u, p):
    ans = 0
    cnt = [0 for _ in range(p)]
    for i in range(n + 1):
        cnt[u[i]] += 1
    for i in range(p):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans


print(solve(u, s, p))

Solution (Python):
from collections import Counter

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

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))

Solution (Python):
n,p=map(int,input().split())
S=input()
M=[0]*p
M[0]=1
ans=0

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

print(ans)

Solution (Python):
n,p=map(int,input().split())
S=input()
M=[0]*p
M[0]=1
ans=0

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

print(ans)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





def toint(l, r):
    return int(''.join(map(str, S[l:r])))


def test():
    ans = 0
    for l, r in itertools.combinations_with_replacement(range(N), r=2):
        s = toint(l, r + 1)
        ans += s % P == 0
    print(ans)


def solve25():
    ret = 0
    for d in range(N):
        if S[d] % P == 0:
            ret += d + 1
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = list(map(int, list(sys.stdin.buffer.readline().decode().rstrip())))


if P in [2, 5]:
    ans = solve25()
    print(ans)
    exit()



powers = []
p = 1
for _ in range(N):
    powers.append(p)
    p = p * 10 % P

s_additions = [0]
s = 0
for i in range(1, N):
    s = (s * 10 + S[i]) % P
    s_additions.append(s)
invs = mod_invs(max=P - 1, mod=P)


def to_index(i, p):
    
    if i == 0:
        return p % P
    return (p - s_additions[i]) * invs[powers[i]] % P


mod_counts = [0] * P
ans = 0
for i, c in enumerate(S):
    mod_counts[to_index(i, c)] += 1
    ans += mod_counts[to_index(i, 0)]
print(ans)