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):


n,p=map(int,input().split())
s=list(map(int,input()))
if p==2 or p==5:
  r=0
  for i in range(n):
    if s[i]%p==0:
      r+=i+1
  print(r)
else:
  c=0
  cnt=[0]*p
  cnt[0]+=1
  for k in range(len(s)-1,-1,-1):
      c=(c+s[k]*pow(10,len(s)-1-k,p))%p
      cnt[c]+=1
  print(sum(x*(x-1)//2 for x in cnt))

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,P=MI()
    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()
    
    
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    now=0
    dd[0]=1
    for i in range(N):
        now=now+(pow(10,i,P)*int(S[-1-i]))
        now%=P
        dd[now]+=1
        
    ans=0
    for k,v in dd.items():
        ans+=(v*(v-1))//2
        
    print(ans)
    

main()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

def modinv(a,p):
    b,u,v = p,1,0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -=t*v
        u,v = v,u
    u %=p
    return u
n,p = ma()
s = input();s=s[::-1]

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

iv10 = modinv(10,p)
ls = [0]*n
for i in range(n):
    a = int(s[i])
    ls[i]=(ls[i-1]+a*pow(10,i,p))%p
co = collections.Counter(ls)
ans=co[0]
tmp=0
for i in range(0,n-1):
    a = int(s[i])
    co[ls[i]%p]-=1
    tmp = (tmp +a)*iv10%p
    r = tmp*pow(10,i+1,p)%p
    ans +=co[r]
print(ans)

Solution (Python):
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num % p == 0:
            ans += i + 1
else:
    bfo, cnt = 0, [1] + [0] * (p - 1)
    for i, num in enumerate(s[::-1]):
        bfo = (bfo + pow(10, i, p) * num) % p
        ans += cnt[bfo]
        cnt[bfo] += 1
print(ans)

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

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

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


prem = [0]*p
prem[0] = 1
curr_rem = 0
ans = 0
s = s[::-1]
for i,si in enumerate(s):
    sii = int(si)
    curr_rem = (sii*pow(10,i,p)+curr_rem)%p
    ans += prem[curr_rem]
    prem[curr_rem] += 1

print(ans)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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:
    lst=[0]*(n+1)
    for i in range(n):
        lst[-2-i]=(lst[-1-i]+int(s[-1-i])*pow(10,i,p))%p
    
    cnt=Counter(lst)
    for i in range(n):
        cnt[lst[i]]-=1
        ans+=cnt[(lst[i]-p)%p]
        
    
    
print(ans)

Solution (Python):
from collections import Counter

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

ans = 0

if p in {2, 5}:
    lst = set(i for i in range(0, 10, p))
    for i, num in enumerate(s):
        if int(num) in lst:
            ans += i + 1
else:
    num = [0]
    for i in range(len(s)):
        tmp = num[-1] + pow(10, i, p) * int(s[-i - 1])
        num.append(tmp % p)
    mod = [0] * p
    for i in num:
        ans += mod[i]
        mod[i] += 1
print(ans)

Solution (Python):
from collections import Counter

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

ans = 0

if p in {2, 5}:
    lst = set(i for i in range(0, 10, p))
    for i, num in enumerate(s):
        if int(num) in lst:
            ans += i + 1
else:
    num = [int(s[-1]) % p]
    for i in range(1, len(s)):
        tmp = num[-1] + pow(10, i, p) * int(s[-i - 1])
        num.append(tmp % p)
    mod = [1] + [0] * (p - 1)
    for i in num:
        ans += mod[i]
        mod[i] += 1
print(ans)

Solution (Python):

import sys
import numpy as np

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


def LI():
    return list(MI())


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

ans = 0
if P == 2:
    for i, s in enumerate(S, 1):
        if int(s) % 2 == 0:
            ans += i
elif P == 5:
    for i, s in enumerate(S, 1):
        if int(s) % 5 == 0:
            ans += i
else:
    cnt = np.zeros(P)
    cnt[0] = 1
    res = 0
    tmp = 1
    for s in S[::-1]:
        res += int(s) * tmp
        res %= P
        cnt[res] += 1
        tmp *= 10
        tmp %= P

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

print(int(ans))

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        num = 0
        point = 1
        for i in S_[::-1]:
            num += int(i) * point
            mod = int(num) % P
            mod_list[mod] += 1
            point *= 10
            point %= P
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, p = map(int, input().split())
s = list(map(int, list(input())))
if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i + 1
    print(ans)
else:
    lis = [0] * p
    cnt = 0
    kurai = 1
    for i in s[::-1]:
        cnt += i * kurai % p
        cnt %= p
        lis[cnt] += 1
        kurai *= 10
        kurai %= p
    ans = 0
    for i in lis:
        ans += i * (i - 1) // 2
    ans += lis[0]
    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,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    A=[0]
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        A.append(num)
        point *=10
        point %=p

    A=Counter(A)
    for i,j in A.items():
        if j>=2:ans +=j*(j-1)//2
print(ans)

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


INF=10**20
def solve(N,P,S,fact):
    ans = 0

    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0
 
        d[0] = 1
        for i in range(N):
            s += S[N-i-1] * fact[i]
            s %= P
            
            d[s] += 1
            
 
        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2
 
    else:
        for i in range(N):
            if S[i] % P == 0:
                ans += i+1

 
    return ans

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 = list(next(tokens))  

    fact = [pow(10,i,P) for i in range(N)]

    S = list(map(int,S))
    S = np.array(S)
    print(solve(N, P, S,np.array(fact)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    
    cc.export('solve', '(i8,i8,i8[:],i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Solution (Python):
from collections import Counter

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

if P in (2, 5):
    ans = sum(i for i, s in enumerate(S, 1) if not int(s) % P)
else:
    Acc = [0] * (N + 1)
    p10 = 1
    for i, s in enumerate(reversed(S)):
        Acc[N - i - 1] = (Acc[N - i] + p10 * int(s)) % P
        p10 = (p10 * 10) % P
    ans = sum(v * (v - 1) // 2 for v in Counter(Acc).values())
print(ans)

Solution (Python):

N, P = map(int, input().split())
S = list(map(int, input()))
if P==2 or P==5:
    ans = 0
    for i, c in enumerate(S, 1):
        if c%P==0:
            ans += i
    print(ans)
    exit()
L = [0] * P
cum = 0
ans = 0
L[0] += 1
inv10 = pow(10, P-2, P)
base = 1
for c in S:
    cum = (cum + c * base) % P
    base = base * inv10 % P
    ans += L[cum]
    L[cum] += 1
print(ans)

Solution (Python):

import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
    allowed_digits = '24680' if p == 2 else '50'
    for i, c in enumerate(s, start=1):
        if c in allowed_digits:
            ans += i
else:
    count = Counter({0: 1})
    x, e = 0, 1
    for c in reversed(s):
        x = (x + (ord(c) - ord('0')) * e) % p
        e = e * 10 % p
        ans += count[x]
        count[x] += 1

print(ans)

Solution (Python):

import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
    allowed_digits = '24680' if p == 2 else '50'
    for i, c in enumerate(s, start=1):
        if c in allowed_digits:
            ans += i
else:
    def minv(x, p):
        return pow(x, p - 2, p)

    count = Counter({0: 1})
    x, delta = 0, 1
    for c in s:
        x = ((x * 10) + ord(c) - ord('0')) % p
        y = (x * minv(delta, p)) % p
        ans += count[y]
        count[y] += 1
        delta = (delta * 10) % p

print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

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

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

cnt = [0] * P
base = 1
cur = 0
for c in S[::-1]:
    cur += (base * int(c)) % P
    cnt[cur % P] += 1
    base *= 10 
    base %= P
ans = 0
for i in cnt:
    if i == 0:
        continue
    ans += i * (i - 1) // 2
print(ans + cnt[0])

Solution (Python):
n, p = [int(i) for i in input().split()]
s = [int(i) for i in list(input())][::-1]
summ  = 0
ans = 0
cnt = [0]*p 
cnt[0] = 1
for i in range(n):
    d = s[i]*pow(10, i ,p)
    summ = (summ + d) %p
    cnt[summ] +=1

if p in [2,5]: 
    if p == 2:
        ok_list = [0,2,4,6,8]
    if p == 5:
        ok_list = [0,5]
    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n-i
else: 
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1)//2 

print(ans)

Solution (Python):
def main():
    _, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]
    ans = 0
    if P == 2:
        for i, v in enumerate(S, start=1):
            if v % 2 == 0:
                ans += i
    elif P == 5:
        for i, v in enumerate(S, start=1):
            if v == 0 or v == 5:
                ans += i
    else:
        cnt = [0]*P
        d = 1
        pre = 0
        cnt[pre] += 1
        for v in S[::-1]:
            v *= d
            v += pre
            v %= P
            cnt[v] += 1
            d *= 10
            d %= P
            pre = v

        ans = sum(cnt[i]*(cnt[i]-1)//2 for i in range(P))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N, P = map(int, input().split())
S = [int(i) for i in input()]
from collections import Counter
def solve(S,N,P):
    if P==2 or P==5:
        ans = 0
        for i in range(N):
            if S[i]%P==0:
                ans += i+1
        return ans
    cum = [0]*(N+1)
    mods = [0]*N
    mods[0] = 1
    for i in range(1,N):
        mods[i] = mods[i-1]*10%P
    for i in range(N):
        cum[i+1] = (cum[i]+S[N-1-i]*mods[i])%P
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S,N,P))

Solution (Python):
N, P = map(int, input().split())
S = input()
total = 0
if P == 2:
  for idx, right_value in enumerate(S, 1):
    if int(int(right_value)%2==0):
      total += idx
elif P == 5:
  valid_options = (0, 5)
  for idx, right_value in enumerate(S, 1):
    if int(int(right_value) in valid_options):
      total += idx
else:
  histo_modsuffix = [0]*P
  previous = 0
  for i, val in enumerate(reversed(S)):
    scale = pow(10, i, P)
    new_val = (previous + scale*int(val))%P
    histo_modsuffix[new_val] += 1
    previous = new_val
  for val in histo_modsuffix:
    total += val*(val-1)//2
  total += histo_modsuffix[0] 
print(total)

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:
    ctr = defaultdict(int)
    ctr[0] = 1
    cur = 0
    for i in reversed(range(N)):
        cur = (cur + int(S[i]) * pow(10, N - i - 1, P)) % P
        ctr[cur] += 1

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

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq

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

ans = 0

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

else:
    d = {0: 1}
    c = 0
    for i in range(n):
        c += (pow(10, i, p)*int(s[n-1-i])) % p
        c %= p
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1

    for dd in d.values():
        ans += dd*(dd-1)//2

print(ans)

Solution (Python):
N,P = map(int,input().split())
S= list(map(int, list(input())))[::-1]
counter = [0]*P
counter[0] = 1
ans = 0
sum = 0
d = 0
r = []
mod = 0

if P != 2 and P != 5:
    mod = 1%P
    for i in range(N):
        d = S[i]*mod
        sum = (sum+d)%P
        mod = (mod*10)%P
        counter[sum] += 1
    for k in range(P):
        ans += (counter[k] * (counter[k]-1)) // 2

if P == 2 or P == 5:
    if P == 2:
        r = [0,2,4,6,8]
    if P == 5:
        r = [0,5]
    for j in range(N):
        if S[j] in r: ans += N - j

print(ans)

Solution (Python):
n, p = map(int, input().split())
s = list(input())
r = [0] * p
ans = 0
if not (p == 2 or p == 5):
    x, t = 0, 1
    for i in range(-1, -(n + 1), -1):
        x += (int(s[i]) * t)
        x %= p
        r[x] += 1
        t *= 10
        t %= p
    for i in r:
        if i >= 2:
            ans += (i * (i - 1) // 2)
    ans += r[0]
else:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += (i + 1)
print(ans)

Solution (Python):
from collections import defaultdict


def main():
    N, P = list(map(int, input().split()))
    S = input()
    if P in [2, 5]:
        ans = 0
        
        for right in range(N - 1, - 1, - 1):
            if int(S[right]) % P == 0:
                ans += right + 1
        print(ans)
        return
    
    
    
    
    
    cur_c = 0
    C = [0] * N
    pw = 1
    for n, s in enumerate(S[::-1]):
        cur_c = (cur_c + pw * int(s)) % P
        C[N - 1 - n] = cur_c
        pw = (pw * 10) % P
    counter = defaultdict(int)
    for c in C:
        counter[c] += 1
    ans = 0
    for c in C:
        counter[c] -= 1
        ans += counter[c]
    ans += len([c for c in C if c == 0])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import groupby
n,p=map(int,input().split())
s=[int(i) for i in input()]
if p==2 or p==5:
    ans=0
    for i in range(n-1,-1,-1):
        
        if s[i]%p==0:
            ans+=(i+1)
    exit(print(ans))
S=[0]*(n+1)
po=[1]*(n+1)
for i in range(n):
    po[i+1]=po[i]*10
    po[i+1]%=p
for i in range(n-1,-1,-1):
    S[i]=S[i+1]+s[i]*po[n-1-i]
    S[i]%=p
t=[[S[i],i] for i in range(n+1)]
t.sort()

u=[[i[1] for i in sorted(list(group))] for key,group in groupby(t,key=lambda x: x[0])]
ans=0
for v in u:
    ans+=(len(v))*(len(v)-1)//2
print(ans)

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

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

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

amari=[0]*P
amari[0]=1

mod=0
for i in range(1,N+1):
  mod=(mod+int(S[-i])*pow(10,i-1,P))%P
  amari[mod]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

Solution (Python):
from collections import Counter
n,p = map(int,input().split())
S = input()
dp = [0]
mod = p
if p==2:
    ans =0
    for i in reversed(range(n)):
        if int(S[i])%2==0:
            ans += i+1
    print(ans);exit()
elif p==5:
    ans =0
    for i in reversed(range(n)):
        if int(S[i])%5==0:
            ans += i+1
    print(ans);exit()
for i in reversed(range(n)):
    dp.append(dp[-1]%mod + pow(10,n-1-i,mod)*int(S[i]))
    dp[-1]%=mod
count = Counter(dp)
ans = 0
for key,val in count.items():
    if val>=2:
        ans += val*(val-1)//2
print(ans)

Solution (Python):
"""
タグ：区間
"""
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
S = input().strip()

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p = p*10%P

    cnt = [0]*P
    for i in range(N+1):
        cnt[T[i]%P] += 1

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

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

Solution (Python):
from math import gcd
from collections import defaultdict

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

answer = 0
if P == 2 or P == 5: 
    for j in range(N - 1, -1, -1): 
        if S[j] % P == 0:
            answer += j + 1
else: 
    
    
    cnts = defaultdict(int)
    suffix = 0
    base = 1
    for i in range(N - 1, -1, -1):
        suffix = (suffix + S[i] * base) % P
        answer += cnts[suffix]  
        answer += 1 if suffix == 0 else 0 
        cnts[suffix] += 1
        base = base * 10 % P

print(answer)

Solution (Python):
from math import gcd
from collections import defaultdict

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

answer = 0
if P == 2 or P == 5:
    for j in range(N - 1, -1, -1): 
        if S[j] % P == 0:
            answer += j + 1
else:
    cnts = defaultdict(int)
    suffix = 0
    base = 1
    for i in range(N - 1, -1, -1):
        suffix = (suffix + S[i] * base) % P
        answer += cnts[suffix]  
        answer += 1 if suffix == 0 else 0 
        cnts[suffix] += 1
        base = base * 10 % P

print(answer)

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

if P == 2:
    ans = 0
    for i, d in enumerate(map(int, S)):
        if d % 2 == 0:
            ans += i+1
    print(ans)
elif P == 5:
    ans = 0
    for i, d in enumerate(map(int, S)):
        if d % 5 == 0:
            ans += i+1
    print(ans)
else:
    mods = [0] * P
    mods[0] = 1
    cur_mod = 0
    for i, digit in enumerate(map(int, S)):
        cur_mod += pow(10, N-i-1, P) * digit
        cur_mod %= P
        mods[cur_mod] += 1

    ans = 0
    for count in mods:
        ans += count * (count - 1) // 2

    print(ans)

Solution (Python):
N,P = map(int,input().split())
S = list(map(int,list(input())))
if P==2:
    cnt = 0
    for i in range(N):
        if S[i]%2==0:
            cnt += i+1
elif P==5:
    cnt = 0
    for i in range(N):
        if S[i]==0 or S[i]==5:
            cnt += i+1
else:
    A = [0 for _ in range(N)]
    a = 0
    b = 1
    for i in range(N-1,-1,-1):
        a = (a+b*S[i])%P
        A[i] = a
        b = (b*10)%P
    C = {i:0 for i in range(P)}
    for i in range(N):
        C[A[i]] += 1
    cnt = 0
    for i in range(P):
        cnt += (C[i]*(C[i]-1))//2
    cnt += C[0]
print(cnt)

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 += i+1
elif P == 5:
    ans = 0
    for i in range(N):
        if S[i] == "0" or S[i] == "5":
            ans += i+1
else:
    L = [0]*P
    num = 0
    for i in range(N):
        num += int(S[N-i-1])*pow(10, i, P)
        num %= P
        L[num] += 1
    ans = L[0]
    for i in range(P):
        ans += L[i]*(L[i]-1)//2

print(ans)

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

if p==2 or p==5:
  ans=0
  for i,ss in enumerate(s):
    if int(ss)%p==0:
      ans+=i+1
  print(ans)
  exit(0)
from collections import Counter
c=Counter()
m=0
c[m]+=1
d=1
s=s[::-1]
for i in range(n):
  m+=int(s[i])*d
  m%=p
  d*=10
  d%=p
  c[m]+=1
ans=0
for v in c.values():
  ans+=v*(v-1)//2
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

s = list(input().strip())

if p == 2 or p == 5:
    ans = 0
    while s:
        if p == 2 and int(s.pop()) % 2 == 0 or p == 5 and int(s.pop()) % 5 == 0:
            ans += n
        n -= 1
    print(ans)
    exit()

a = [0] * p

i = 1
k = 0
while s:
    k = (k + int(s.pop()) * i) % p
    a[k] += 1
    i *= 10
    i %= p

ans = a[0]
for i in a:
    if i >= 2:
        ans += i * (i - 1) // 2
print(ans)

Solution (Python):
n,p=map(int,input().split())
s=input()
total=[0]*p
total[0]=1
t=[0]*(n+1)
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:
    for i in range(n-1,-1,-1):
        t[i]=t[i+1]%p+int(s[i])*pow(10,n-1-i,p)
        total[t[i]%p]+=1
    ans=0
    for i in range(p):
        ans+=total[i]*(total[i]-1)//2
    print(ans)

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

Solution (Python):
import collections, sys
N, P = map(int, input().split())
S = input()
s_mod = [0]*(N+1)

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


for i in range(N):
    s_mod[i+1] = (pow(10, i, P) * int(S[-(i+1)])+s_mod[i]) % P
c = collections.Counter(s_mod)
for v in c.values():
    ans = (ans + v*(v-1)//2)
print(ans)

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

c = [0 for i in range(p)]
c[0] = 1
x = 0
ans = 0
for i,j in enumerate(s[::-1]):
  if p == 2 or p == 5:
    if int(j)%p == 0:
      ans += n-i
  x = (x + int(j)*pow(10,i,p))%p
  c[x] += 1
if ans:
  print (ans)
  exit()
for i in range(p):
  ans += (c[i]*(c[i]-1))//2
print (ans)

Solution (Python):
from math import factorial
import collections

def permutations_count(n, r):
    ''' 順列 '''
    return factorial(n) // factorial(n - r)


def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))


n,p = map(int, input().split())
S = input()
su = 0

if p > 6 or p == 3:

    lis = []
    amari = 1
    lis.append(int(S[-1]) % p)

    for i in range(2, len(S)+1):
        amari = (amari * 10) % p
        lis.append((int(S[-1*i]) * amari + lis[i-2]) % p)

    c = collections.Counter(lis)

    for k in c:
        if c[k] > 1:
            su += combinations_count(c[k], 2)

    su += c[0]

    print(su)

else:
    S = S[::-1]
    for i in range(len(S)):
        if int(S[i]) % p == 0:
            su += len(S)-i
    print(su)

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

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  mods = [0] * (N+1)
  for i in range(N-1, -1, -1):
    mods[i] = (int(S[i])*pow(10, N-i-1, P)+mods[i+1]) % P
  c = dict()
  for m in mods:
    c[m] = c.get(m, 0)+1
  for key in c:
    ans += c[key]*(c[key]-1)//2

print(ans)

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

mods = [0] * (N+1)
for i in range(N-1, -1, -1):
  mods[i] = (int(S[i])*pow(10, N-i-1, P)+mods[i+1]) % P
c = dict()
for m in mods:
  c[m] = c.get(m, 0)+1

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for key in c:
    ans += c[key]*(c[key]-1)//2

print(ans)

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

mods = [0] * (N+1)
for i in range(N-1, -1, -1):
  mods[i] = (int(S[i])*pow(10, N-i-1, P)+mods[i+1]) % P
c = dict()
for m in mods:
  c[m] = c.get(m, 0)+1

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c[mods[i]]

print(ans)

Solution (Python):
n,p = map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:
    for i,c in enumerate(s,1):
        if int(c)%p == 0: ans += i
else:
    cnt = [0]*p
    cnt[0] = 1
    x = 0
    d = 1
    for c in s[::-1]:
        x += d*int(c)
        x %= p
        cnt[x%p] += 1
        d *= 10
        d %= p
    
    for v in cnt: ans += v*(v-1)//2
print(ans)

Solution (Python):
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = 0
    modDict = defaultdict(int)
    modDict[0] += 1
    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):
            modSum += int(S[N-i-1]) * pow(10, i, P)
            modSum %= P
            modDict[modSum] += 1

        for key in modDict:
            v = modDict[key]
            ans += v * (v - 1) // 2
    
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

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

if P in {2, 5}:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
else:
    ans = 0
    T = [0]*P
    T[0] = 1
    tmp = 0
    k = 1
    for s in reversed(S):
        tmp = (tmp + k * int(s)) % P
        k = k * 10 % P
        ans += T[tmp]
        T[tmp] += 1

print(ans)

Solution (Python):

def m():
    n,p=map(int,input().split())
    now=0
    s=input()
    if p==2 or p==5:
        ans=0
        for i in range(n):
            if int(s[i])%p:continue
            ans+=i+1
    else:
        table=[0]*p
        table[0]=1
        c=1
        for i in range(n-1,-1,-1):
            now=(now+c*int(s[i]))%p
            c=10*c%p
            table[now]+=1
        ans=sum(j*(j-1)//2 for j in table)

    print(ans)
if __name__ == "__main__":
    m()

Solution (Python):

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:
    l = [1]+[0]*(P-1)
    tmp = 0
    r10 = 1
    for i in range(N-1,-1,-1):
        tmp = (r10*int(S[i])+tmp)%P
        l[tmp] += 1
        r10 = (r10*10)%P
    for x in l:
        ans += x*(x-1)//2
print(ans)

Solution (Python):
import sys 
import collections
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,P = map(int,readline().split())
S = list(map(int,readline().rstrip().decode()))

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

print(solve(S))