Problem:


Score : 500 points

Problem Statement

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

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

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

Compute this count to help Takahashi.

Constraints

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

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

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

Sample Input 1

4 3
3543

Sample Output 1

6

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

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

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

Sample Input 2

4 2
2020

Sample Output 2

10

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

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Accepted

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

def nC2(n):
    if n == 0:
        return 0
    return n*(n-1)//2

p_joyo = [] # 10^m % p は p_joyo[m]に対応
r = 1
for i in range(n):
    p_joyo.append(r)
    r = r*10 % p

if p != 2 and p != 5:
    u = []
    r = int(s[n-1])%p
    for i in range(1,n):
        u.append(r)
        j = n-i-1
        r = (r + int(s[j])*p_joyo[i])%p
    u.append(r)
    onaji = {}
    for i in u:
        if not i in onaji:
            onaji[i] = 1
        else:
            onaji[i] += 1
    ans = 0
    for key, r in onaji.items():
        ans += nC2(r)
        if key == 0:
            ans += r
    print(ans)

elif p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0,2,4,6,8]:
            ans += i+1
    print(ans)

else:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0,5]:
            ans += i+1
    print(ans)

Submission status: Accepted

Solution code:
N,P=map(int,input().split())
S=[int(i) for i in list(input())][::-1]
if P==2 or P==5:
    ans=0
    for i in range(N):
        if S[i]%P==0:
            ans+=N-i
    print(ans)
else:   
    X=[0 for i in range(N+1)]
    tmp=1
    for i in range(N):
        X[i+1]=X[i]+tmp*S[i]
        X[i+1]%=P
        tmp=tmp*10
        tmp%=P
    #print(X)
    D=dict()
    for i in range(N+1):
        if X[i] in D:
            D[X[i]]+=1
        else:
            D[X[i]]=1
    ans=0
    for k in D:
        ans+=(D[k]*(D[k]-1))//2
    #print(D)
    print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi#, gcd
from fractions import gcd
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s, sep = ''):
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e == None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def main():
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    d.reverse()

    if 10%P == 0:
        ans = 0
        for l in range(N):
            if d[l] % P == 0:
                ans += N-l
        print(ans)
        return 0

    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P
    
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

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

    print(ans)
    return 0


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

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

    T = [0] * P
    T[0] = 1

    ss, p10 = 0, 1
    for s1 in S[::-1]:
        ss += p10 * s1
        ss %= P
        T[ss] += 1
        p10 = 10 * p10 % P

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
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):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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
# MOD = 998244353


# 解説
# P で割り切れるなら 10^n で割っても割り切れる。
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[i]: int(S[i:]) % P
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)):
    # U[i] を引いたときに 0 (mod P) となる数
    counts[U[i]] -= 1
    ans += counts[U[i]]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
    # s_cant = [0 if i == 1 else 0 for i in s_can]
    # s_acc = list(accumulate(s_can[::-1]))[::-1]
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
if 10 % p == 0: # p = 2, 5
    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)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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')

#solve
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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
if 10 % p == 0: # p = 2, 5
    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)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 参考: https://drken1215.hatenablog.com/entry/2020/03/08/020200
# 注: (mod p(素数)上で) aとpが互いに素のとき、aの逆元とpが互いに素になることは容易に証明できる（aの逆元 = a^(p-2)なので）

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def e_divisible_substring():
    # 参考: https://atcoder.jp/contests/abc158/submissions/10611866
    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]  # 下の桁から見ていく
    # editorial の U_i mod P の計算
    u = [0] * N
    u[0] = s[0] % P
    power = 1
    for i in range(1, N):
        power *= 10
        power %= P  # S の桁数は最大 20万 なので、この処理は必要
        u[i] = u[i - 1] + power * s[i]
        u[i] %= P
    # 配列 u における、値が等しいインデックス 2 つを選ぶと、そのインデックスが表す
    # 2 つの整数の差は P の倍数になる
    # 値が 0 のインデックスについては、それ単体が P の倍数である
    counter = Counter(u)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]

print(e_divisible_substring())

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    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): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    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)

Submission status: Accepted

Solution code:
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:
            # If P == 2
            # all substring ending here with last digit even
            # If P == 5
            # all substring ending here with last digit 5 or 0
            total += i + 1
    print(total)
else:
    # Note P is relatively prime with 10

    # If S is '1234'
    # Want suffixes:
    # s[4] = 1234
    # s[3] =  234
    # s[2] =   34
    # s[1] =    4
    # s[0] =    0
    #
    # Then s[j] - s[i] gives the value of the number int(S[-j:-i]) * 10**(N -i)
    # Since P doesn't divide 10, if P divides s[j] - s[i] it also divides the number

    CHECK = False
    suf = [0]
    power = 1
    for x in reversed(S):
        suf.append(suf[-1] + x * power)
        power *= 10
        if not CHECK:
            # Don't mod when checking
            suf[-1] %= P
            power %= P
    if CHECK:
        # 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)

    # Count number of s[j] - s[i] pairs that are 0 mod P
    total = 0
    counts = Counter()
    for x in suf:
        x = x % P
        total += counts[x]
        counts[x] += 1
    print(total)

Submission status: Accepted

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

Submission status: Accepted

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

res = 0

if P == 2 or P == 5:
    # Corner case
    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
        
    # Combination
    for p in range(P):
        res += val[p] * (val[p] - 1) // 2
    
print(res)

Submission status: Accepted

Solution code:
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) # right
    #print(N,P,S)
    #print(res)

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#e
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)