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:
from collections import Counter
N, P = map(int, input().split())
S = input()

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

    ans = 0
    cnt = Counter(T[1:])
    for p in range(P):
        x = cnt[p]
        ans += x * (x - 1) // 2
    ans += cnt[0]
    return ans

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

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

Submission status: Accepted

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p:
  s = reversed(s)
a = enumerate(map(int, s), 1)
if 10 % p == 0:
  r = sum(i for i, x in a if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in a:
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Accepted

Solution code:
I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  d = {0 : 1}
  t, y = 0, 1
  for i, x in enumerate(I(reversed(s)), 1):
    t = (t + x * y) % p
    d[t] = d.get(t, 0) + 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d.values())
print(r)

Submission status: Accepted

Solution code:
I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(I(reversed(s)), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(I(reversed(s)), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Accepted

Solution code:
n,p = map(int,input().split())
s = list(map(int,(list(input()))))
def keychange(dic,x):
    newdic = {}
    for k in dic:
        b = (k*10 + x) % p
        newdic[b] = dic[k]
    return newdic
count = 0
if p == 2:
    for i in range(n):
        if s[i] % 2 == 0:
            count += i+1
    print(count)
    exit()
if p == 5:
    for i in range(n):
        if s[i] % 5 == 0:
            count += i+1
    print(count)
    exit()
inv_t = [0]+[1]
for i in range(2,p):
  inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
dic = {}
memory = [1,0]
for i in range(n):
    x = s[i] % p
    memory[0] = 10*memory[0] % p
    memory[1] = (10*memory[1] + x) % p
    xinv = inv_t[memory[0]]*(x-memory[1]+p) % p
    if xinv in dic:
        dic[xinv] += 1
    else:
        dic[xinv] = 1
    zeroinv = (p-memory[1])*inv_t[memory[0]] % p
    if zeroinv in dic:
        count += dic[zeroinv]
print(count)

Submission status: Accepted

Solution code:
n, P = map(int, input().split())
S = input()
ans = 0
#----------------------------------------------
# 1.
# int(S[a:b]) * 10 ** (n - b) == (int(S[a: n]) - int(S[b: n])) で表される
# 例
# S = 1234
# a = 1, b = 3 のとき
# 23 = (234 - 4) // 10 ** (4 - 3)
#    =  230 // 10
#    =  23
#
# 2.
# Pは素数のため　P = 2, 5　のとき以外は　１０の約数でない
# A * (10 ** x) が Pで割れるとき　A は P の倍数　(x は任意定数)
#
# 3.
# 1. の式を mod P で考える
# int(S[a: b]) * 10 ** (n - b) == (int(S[a: n]) - int(S[b: n]))
# ⇒　(S[a: b] * 10 ** (n - b)) % P == (S[a: n] - S[b: n]) % P  (mod P)
# ⇒　(S[a: b] % P) * (10 ** (n - b) % P) == (S[a: n] % P) - (S[b: n] % P)  (mod P)
# 2.より P = 2, 5以外のときは 10 ** (n - b) % P != 0となるため
# (S[a: n] % P) - (S[b: n] % P)　= 0　すなわち　(S[a: n] % P) == (S[b: n] % P)のとき
# S[a:b] % P　= 0である
#
# これより
# S[i: n] % P (0 <= i < n) を求めれば
# 以下のコードのようにS[i: j] % P を求めることができる (0 <= i < n, i <= j < n)
#----------------------------------------------
#まずS[i: n] % P (0 <= i < n) を求める (remain に格納する)
remain = [0] * P
remain[0] += 1
d = 1
left = 0
for i in range(n):
    # print(left)
    left = (left + int(S[n - i - 1]) * d) % P
    remain[left] += 1
    d = d * 10 % P
# print(remain)
for r in remain:
    ans += r * (r - 1) // 2
#----------------------------------------------
# 4.P = 2, 5　のときについて考える
#     1. P = 2 のとき
#         ある数の下１桁が2の倍数のとき、その数は2の倍数であるため
#         S[i] % 2 == 0 のとき
#         S[h:i] % 2 == 0 (0 <= h <= i)
#         よって以下のようなコードで答えを求めることができる
#----------------------------------------------
if P == 2:
    ans = 0
    for i in range(n):
        if int(S[i]) % 2 == 0:
            ans += i + 1
    print(ans)
#----------------------------------------------
    # 2. P = 5 のときもP = 2 のときと同様に考えれば良いため
#----------------------------------------------
if P == 5:
    ans = 0
    for i in range(n):
      if int(S[i]) % 5 == 0:
          ans += i + 1
    print(ans)
if P != 2 and P != 5:
    print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,p=LI()
  s=S()

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

  _s=list(s)
  _s.reverse()

  a=[]
  i=1
  for x in _s:
    b=(i*int(x))%p
    a.append(b)
    i*=10
    i%=p

  b=[0]*p
  b[a[0]%p]=1
  for i in range(n-1):
    a[i+1]+=a[i]
    a[i+1]%=p
    b[a[i+1]]+=1

  for i,x in enumerate(b):
    if i==0:
      ans+=x
    if x>1:
      ans+=x*(x-1)//2

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

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

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * pow(10, i, P)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    # u = [int(s[i:]) for i in range(n)]
    remainders = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += pow(10, i, p) * int(char)
        remainders.append(t % p)
    remainders = remainders[::-1]
    remainders.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
mod = P
Cum = []
S.reverse()

if 10%P!=0: 
    temp = 0
    power = 1
    for i in range(N):
        temp += (S[i]*power)%mod
        temp %= mod
        power *= 10
        power %= mod
        Cum.append(temp)

    from collections import Counter

    counter=Counter(Cum)

    counter[0]+=1

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

else:
    ans = 0
    S.reverse()
    for i in range(N):
        if S[i]%P==0:
            ans += (i+1)          
    print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import Counter

N, P = map(int, input().split())
S = list(map(int,list(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))

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
rui = [0] * (N + 1)
if 10 % P == 0:
    for i in range(len(S)):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()

t = 1
for i in reversed(range(N)):
    tmp = int(S[i]) * t % P
    rui[i] = (rui[i + 1] + tmp) % P
    t *= 10
    t %= P

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N,p=map(int,input().split())
s=input()
res=0
dic=dd(int)
c = [0]*(N+1)

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

for i in range(N):
    now = int(s[N-i-1])%p
    c[i+1] = (c[i]+pow(10,i,p)*now)%p
for val in c:
    dic[str(val)] += 1
    if dic[str(val)] >= 2:
        res += dic[str(val)]-1
print(res)

Submission status: Accepted

Solution code:
def main():
  N,P = map(int,input().split())
  S = list(map(int,list(input())))
  S=S[::-1]
  ans = 0
  if P==2:
    l = [0,2,4,6,8]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i
  elif P==5:
    l=[0,5]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i

  else:
    l = [0]*P
    a=0
    for i in range(N):
      b = pow(10,i,P)
      b *= S[i]
      b %= P
      a+=b
      a%=P
      l[a]+=1
    ans+=l[0]
    for i in l:
      ans+=i*(i-1)//2

  print(ans)
  
main()

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline

N, P = map(int, input().split())
S=input().strip()
if P in {2, 5}:
    r=0
    for i in range(N):
        if not int(S[i])%P:
            r+=i+1
    print(r)
else:
    S = S[::-1]
    r=0
    from collections import defaultdict
    d=defaultdict(int)
    d[0] += 1
    R=0
    X=1
    for i in range(N):
        r += int(S[i])*X
        R += d[r%P]
        X = (X*10)%P
        d[r%P]+=1
    print(R)

Submission status: Accepted

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

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mod = [-1 for i in range(p)]
    mod[0] = 0
    mp = 0
    m10 = 1
    
    for i in range(n-1, -1, -1):
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1
        m10 = (10 * m10) % p

    for m in mod:
        ans += m*(m+1)//2

print(ans)

Submission status: Accepted

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        mp = (mp + int(s[i]) * m10) % p
        m10 = (10 * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
mod = [0]*P
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)
else:
    un1 = 0
    un = 0
    for i in range(N-1, -1, -1):
        #a =int(S[i])*10**un + un1
        a =int(S[i])*pow(10,un,P)+(un1)%P
        un += 1
        un1 = a
        mod[a%P]+=1
    ans += mod[0]  
    for i in range(P):
        ans += mod[i]*(mod[i]-1)/2
    print(int(ans))

Submission status: Accepted

Solution code:
#
import sys
import math
#import numpy as np
import itertools
from collections import Counter
# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    d=1
    for i in range(n-1,-1,-1):
        q = (d*s[i]+q)%p
        x.append(q)
        d = (d * 10)%p
    #print(x)
    counter = Counter(x)
    #print(counter)

    for k in counter:
    #    print(k)
        if k==0:
            answer += counter[k] * (counter[k]+1) // 2
        else:
            answer += counter[k] * (counter[k]-1) // 2

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        m10 = (10 * m10) % p
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * pow(10, N - n - 1, P)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)

Submission status: Accepted

Solution code:



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

ans = 0
mod_P = [0] * P
mod_P[0] += 1
# P が 10と互いに素でないなら、U_i - U_jのうちのU_jがPで割り切れるだけでよい
if P in [2,5]:
    
    for i in range(N):
            """
            今見ているiかそれより左側にある物をU_iとして選択する場合に割り切れるようになるので、
            いまのiを含む左にあるものの個数を足す
            """
            if int(S[i]) % P == 0:
                ans += i+1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく(今回みたいな大きな値について毎回modをとるとめちゃくちゃ遅い)

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i, P) + curr
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,p=map(int,input().split())
A=list(map(int,input()))
def U(x):
    return int(A[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(A[i])%p==0:
            ans+=keta
    print(ans)
    exit()
    
acc = [0 for i in range(n)] 
cur = A[-1] % p
acc[-1] = cur
k = 1
for i in range(n-2, -1, -1):
    cur += pow(10, k, p) * A[i]
    cur %= p
    acc[i] = cur
    k += 1
acc = acc + [0]
 
C = Counter(acc)
ans = 0
for v in C.values():
    ans += v * (v-1) // 2
print(ans)

Submission status: Accepted

Solution code:
#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*pow(10,n-i,p)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Accepted

Solution code:
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


n, p = _ia()
u = [1 if i == 0 else 0 for i in range(p)]
s = _s()
cnt = 0
if p == 2 or p == 5:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += i + 1
else:
    b = 1
    m10 = 10 % p
    prev = 0
    for c in s[::-1]:
        ui = prev = (prev + int(c) * b) % p
        b = (b*m10) % p
        cnt += u[ui]
        u[ui] += 1
print(cnt)

Submission status: Accepted

Solution code:
# 参考にさせていただいたもの
# https://atcoder.jp/contests/abc158/submissions/10620169
# mulをpow(10,桁数,P)ではなく、ループ中に10倍ずつする方法
# counterに収められたある剰余をとる集合の大きさからnC2でペア数を求める方法

def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        mul = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * mul) % P
            counter[curr_num] += 1
            mul = (mul * 10) % P

        def choose_2(x):
            return x * (x - 1) // 2

        ret = sum(choose_2(cnt) for cnt in counter)
        print(ret)
        return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        mul = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * mul) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
            mul = (mul * 10) % P
        print(ret)
        return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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:
    s_inv = s[::-1]
    lst = [0 for i in range(n+1)]
    n_amari = [0 for i in range(p)]
    amari = 1
    ans = 0
    for i in range(n):
        amari = (amari * 10) % p
        lst[i+1] = (amari * int(s_inv[i]) + lst[i]) % p
        if lst[i+1] != 0:
            ans += n_amari[lst[i+1]]
            n_amari[lst[i+1]] += 1
        else:
            n_amari[lst[i+1]] += 1
            ans += n_amari[lst[i+1]]
    print(ans)

Submission status: Accepted

Solution code:
N,P = map(int,input().split())
s = list(input())
S = [0]*N

for i in range(N):
    S[i] = int(s[i])

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (pow(10,(i-1),P) )
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

else:
    if P == 2:
        for i in range(N):
            if S[i] %2 == 0:
                count += i+1
    if P == 5:
        for i in range(N):
            if S[i] %5 == 0:
                count += i+1

print(count)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()
# 累積和
remain = [0] * N
cur = 0
answer = 0
S_rev = S[::-1]
power = 1
for i in range(N):
    if i >= 1:
        power *= 10
        power %= P
    num = cur + power * int(S_rev[i])
    cur = num % P
    remain[i] = cur

if P == 2 or P == 5:
    ind = (i for i, x in enumerate(S, 1) if int(x) % P == 0)
    answer = sum(ind)

else:
    counter = Counter(remain)
    answer += counter[0]
    for k, v in counter.items():
        answer += v * (v-1) // 2

print(answer)

Submission status: Accepted

Solution code:
def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * pow(10, i, P)) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
        print(ret)
        return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:#右端を固定すれば2,5で割り切れるならそれ以降は全部いけるのでn-iをたす
    for i in range(n):
        if int(s[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
else:
  s = s[::-1]#反転させてしたからみる
  cnt = [0]*p # pで割った時のあまり
  cnt[0] = 1 # 0の時はなにも取らない時全体も入るので+1する
  modp = 0
  for i,c in enumerate(map(int,s)):#enumerateでiterator i , s[i]の値cを同時に取得
    modp = (c*pow(10,i,p) + modp)%p
    cnt[modp] += 1
  for i in range(p):
    ans += cnt[i]*(cnt[i]-1) //2
  print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
n,p=map(int,input().split())
s=list(input())
s.reverse()
ans=0

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

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

l=[0,int(s[0])%p]
x=int(s[0])
y=1
for i in range(1,n):
  y*=10
  y%=p
  x+=(y*int(s[i]))%p
  x%=p
  l.append(x)
L=collections.Counter(l)
for j in L.values():
  ans+=j*(j-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys,bisect
input = sys.stdin.readline

n,p = map(int,input().split())
s = list(input())
for i in range(n):
    s[i] = int(s[i])
    
if p == 2 or p == 5:
    res = 0
    for i in range(n):
        if s[i]%p == 0:
            res += i+1
    print(res)
else:
    d = 1
    q = [0]
    for i in range(n-1,-1,-1):
        q.append((q[-1]+s[i]*d)%p)
        d = d*10%p
    q.sort()
    res = 0
    q.append(-1)
    f = 1
    for i in range(n+1):
        if q[i]==q[i+1]:
            f += 1
        else:
            res += f*(f-1)//2
            f=1
    print(res)

Submission status: Accepted

Solution code:
import sys
import collections
n,p=map(int,input().split())
s=list(input())
s.reverse()
ans=0

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

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

l=[0,int(s[0])%p]
x=int(s[0])
y=1
for i in range(1,n):
  y*=10
  y%=p
  x+=(y*int(s[i]))%p
  x%=p
  l.append(x)
L=collections.Counter(l)
for j in L.values():
  ans+=int(j*(j-1)/2)
print(ans)

Submission status: Accepted

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
else:
    pr = 0
    rcntmap = [0] * P
    rcntmap[0] = 1  # r - 0 patten
    for i in reversed(range(len(S))):
        d = int(S[i])
        r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
        #r = int(S[i:]) % P
        ans += rcntmap[r]
    
        rcntmap[r] += 1
        pr = r

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

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


mods = [0 for _ in range(P)]
count = 0

loop = 0
mod = 0

if P != 2 and P != 5: 
  for digit in S[::-1]:
    loop += 1
    digit = int(digit)
    mod = (mod + digit*pow(10,loop-1,P))%P
    count += mods[mod]
    mods[mod] += 1
    if mod == 0:
      count += 1
else:
  for digit in S:
    loop += 1
    if int(digit)%P == 0:
      count += loop


  

print(count)

Submission status: Accepted

Solution code:
import sys

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

if P in [2, 5]:
    ans = 0
    if P == 2:
        ok = [0, 2, 4, 6, 8]
    else:
        ok = [0, 5]
        
    for i in range(N):
        if S[i] in ok:
            ans += N - i
    print(ans)
    sys.exit()

cnt = [0] * P
cnt[0] = 1

s = 0
for i in range(N):
    d = S[i] * pow(10, i, P)
    s += d
    s %= P
    cnt[s] += 1

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

print(ans)

Submission status: Accepted

Solution code:
N,P = map(int,input().split(" "))
S = input()
ans = 0
if P in [2,5]:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    lis = [0 for _ in range(N+1)]
    ten = 1
    for i in reversed(range(N)):
        tmp = int(S[i])*ten%P
        lis[i] = (lis[i+1]+tmp)%P
        ten *= 10
        ten %= P
    cnt = [0 for _ in range(P)]
    for i in reversed(range(N+1)):
        ans += cnt[lis[i]]
        cnt[lis[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split());s,n,N,c,d=map(int,list(input())),1,0,0,[0]*p
if p!=5:
 for i in s:N,a=(N*10+i)%p,pow(n,p-2,p);d[(i-N)*a%p]+=1;c+=d[-N*a%p];n=n*10%p
else:c=sum([j+1 for j,i in enumerate(s)if i%5==0])
print(c)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
s=input().rstrip()
ans=0
l=[0]*p
a=[0,1,2,3,4,5,6,7,8,9]
c=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):
        # mod=int(s[-(i+1):])%p
        mod=(c+a[int(s[-(i+1)])])%p
        ans+=l[mod]
        l[mod]+=1
        if mod==0:
            ans+=1
        c=mod
        
        for j in range(10):
            a[j]=a[j]*10%p
 
print(ans)

Submission status: Accepted

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

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