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: Wrong Answer

Solution code:
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

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

    ans = 0
    if not P % 10 == 0:
        d = [0] * (P+1)
        s = 0

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

        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2

    else:
        target = [0,5] if P == 5 else [0,2,4,6,8]
        for i in range(N):
            if int(S[i]) in target:
                ans += i+1



    print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    N,P=map(int,input().split())
    S = list(map(int,input()))
    ans = 0
    if not P % 10 == 0:
        d = [0] * (P+1)
        s = 0

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

        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2

    else:
        target = [0,5] if P == 5 else [0,2,4,6,8]
        for i in range(N):
            for t in target:
                if S[i] == target:
                    ans += N-(i+1)



    print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a = [0]
  s1 = s[::-1]
  b=1
  for i in range(n):
    a.append((int(s1[i])*pow(10,i,p))%p)
  a = a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a = [0]
  s1 = s[::-1]
  b=1
  for i in range(n):
    a.append((int(s1[i])*b)%p)
    b*=10%p
  a = a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a = [0]
  s1 = s[::-1]
  b=1
  for i in range(n):
    a.append((int(s1[i])*b)%p)
    b*=10
  a = a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a = [0]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])*pow(10,i))%p)
  a = a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a = [0]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])*pow(10,i))%p)
  a = a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=i*(i-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

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

s = input()

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

for i in range(0, n)[::-1]:
    ruisekiwa[n - i] = ((ord(s[i]) - ord('0')) * (10 ** i) + ruisekiwa[n - i - 1]) % p

ans = 0
cnt = [0 for _ in range(0, p)]
for i in range(0, n+1):
    ans += cnt[ruisekiwa[i]]
    cnt[ruisekiwa[i]] += 1

print(ans)

Submission status: Wrong Answer

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

s = input()

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

for i in range(0, n)[::-1]:
    ruisekiwa.append(((ord(s[i]) - ord('0')) * (10 ** i) + ruisekiwa[n - i - 1]) % p)

ans = 0
cnt = [0 for _ in range(0, p)]
for i in range(0, n+1):
    ans += cnt[ruisekiwa[i]]
    cnt[ruisekiwa[i]] += 1

print(ans)

Submission status: Wrong Answer

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

s = input()

ruisekiwa = [0]

for i in range(0, n)[::-1]:
    ruisekiwa.append(((ord(s[i]) - ord('0')) * (10 ** i) + ruisekiwa[n - i - 1]) % p)

ans = 0
cnt = [0 for _ in range(0, p)]
for i in range(0, n+1):
    ans += cnt[ruisekiwa[i]]
    cnt[ruisekiwa[i]] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
n,p = [int(x) for x in input().split()]
s = deque("0"+input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a = int("".join(s))
  r[a%p]+=1
  for i in range(n):
    s.popleft()
    #print(s)
    a = int("".join(s))
    r[a%p]+=1
  #print(r)
  ans = 0
  cnt=1
  for i in r.values():
    ans+=i*(i-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = defaultdict(int)
  a = int(s)
  r[a%p]+=1
  for i in range(n):
    a = a//10
    r[a%p]+=1
  #print(r)
  ans = 0
  cnt=1
  for i in r.values():
    ans+=i*(i-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 or p!=5:
  r = [0]
  for i in range(n):
    a = int(s[i:])%p
    r.append(a)
  #print(r)
  r.sort()
  ans = 0
  for key, group in itertools.groupby(r):
    l = len(list(group))
    ans +=l*(l-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 or p!=5:
  r = [0]
  for i in range(n):
    a = int(s[i:])%p
    r.append(a)
  #print(r)
  r.sort()
  ans = 0
  for key, group in itertools.groupby(r):
    l = len(list(group))
    ans +=l*(l-1)//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i
  print(ans)

Submission status: Wrong Answer

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

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

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    # print(U)
    
    c = 0
    for i in range(P):
    
        m = U.count(i)
        c += m*(m-1)//2
    print(c)

Submission status: Wrong Answer

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

U = [0]
a = 0
t = 1

for i in range(N):
    t %= P
    a += int(S[-i-1])*t
    a %= P
    t *= 10
    U.append(a)
# print(U)

c = 0
for i in range(P):

    m = U.count(i)
    c += m*(m-1)//2
print(c)

Submission status: Wrong Answer

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

U = [0]
a = 0

for i in range(N):
    a += int(S[-i-1])*(pow(10,i)%P)
    a %= P
    U.append(a)
# print(U)

c = 0
for i in range(P):

    m = U.count(i)
    c += m*(m-1)//2
print(c)

Submission status: Wrong Answer

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

U = [0]
a = 0

for i in range(N):
    a += int(S[-i-1])*(pow(10,i)%P)
    a %= P
    U.append(a)
print(U)

c = 0
for i in range(P):

    m = U.count(i)
    c += m*(m-1)//2
print(c)

Submission status: Wrong Answer

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

U = []

for i in range(N):
    u = int(S[i:])%P
    U.append(u)
U.append(0)

# print(U)

c = 0
for i in range(P):
    m = U.count(i)
    c += m*(m-1)//2
print(c)

Submission status: Wrong Answer

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

for i in range(1,N+1):
    u = int(S[:i])%P
    U.append(u)

c = 0
for i in range(P):
    m = U.count(i)
    c += m*(m-1)//2
print(c)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import collections
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + 1 + 1
    print(ret)
else:
    c_list = [0] * n
    for i in range(len(s)):
        c_list[i] = int(s[-i-1:]) % p
    c_list.append(0)
    c = collections.Counter(c_list)
    ret = 0
    for item in c:
        cnt = c[item]
        if cnt >= 2:
            ret = ret + combinations_count(cnt, 2)
    print(ret)

Submission status: Wrong Answer

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + 1 + 1
    print(ret)
else:
    c_list = [0] * n
    for i in range(len(s)):
        c_list[i] = int(s[-i-1:]) % p
    c_list.append(0)
    c_set = set(c_list)
    ret = 0
    for item in c_set:
        cnt = c_list.count(item)
        if cnt >= 2:
            ret = ret + combinations_count(cnt, 2)
    print(ret)

Submission status: Wrong Answer

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + 1 + 1
    print(ret)
else:
    c_list = [0] * n
    for i in range(len(s)):
        c_list[i] = int(s[-i-1:]) % p
    c_list.append(0)
    ret = 0
    for i in range(p):
        cnt = c_list.count(i)
        if cnt >= 2:
            ret = ret + combinations_count(cnt, 2)
    print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

tmp = ''
count = defaultdict(int)
for s in S:
  tmp = s + tmp
  res = int(tmp) % P
  count[res] += 1
  
ret = count[0]
for v in count.values():
  ret += v * (v - 1) // 2

print(ret)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, p = map(int, input().split())
s = input()

ma = 2 * 10**5
ar = np.arange(ma)
ar = ar[ar%p == 0]
count = 0
for k in ar:
    count += s.count(str(k))
print(count)

Submission status: Wrong Answer

Solution code:
N, P = input().split()
s = input()
cnt = 0
for i in range(len(P), int(N)+1):
  for j in range(int(N) - i + 1):
    k = int(s[j:j+i])
    if k % int(P) == 0:
      cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

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

cnt = defaultdict(int)
cnt[0] = 1
ans = 0
now = 0

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

print(ans)

Submission status: Wrong Answer

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

l = [0]*p
res = 0
l[0] = 1

for i in range(n):
  l[int(s[i:])%p] += 1

for e in l:
  if e:
  	res += e*(e-1)//2
  
print(res)

Submission status: Wrong Answer

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

l = [0]*p
res = 0
l[0] = 1

for i in range(n):
  l[int(s[i:])%p] += 1

for e in l:
  res += e*(e-1)//2
  
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

crem = 0
res = 0
dic_p = defaultdict(lambda : 0)
for i,subs in enumerate(s[::-1]):
    crem += (int(subs) * 10**int(i)) % p
    crem %= p
    
    if crem == 0:
        res += 1
    res += dic_p[crem]

    dic_p[crem] += 1
    
print(res)

Submission status: Wrong Answer

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

if 10%P==0:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=(i+1)
    print(ans)
else:
    AMARI=1
    L=[1]
    for i in range(1,N):
        L.append((L[-1]*10)%P)
    #print(L)
    for i in range(N):
        L[i]=(L[i] * int(S[i]))%P
    #print(L)
    LR=[L[0]]
    for i in range(1,N):
        LR.append((LR[-1]+L[i])%P)
    #print(LR)
    D={}
    D[0]=1
    for i in range(N):
        if LR[i] not in D:
            D[LR[i]]=1
        else:
            D[LR[i]]+=1
    ans=0
    for i,j in D.items():
        ans+=j*(j-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
class Solution:

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

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  # int(S[i,N] mod P
            U[0] += 1
            for i in range(N):
                U[int(S[i:N]) % P] += 1

            for u in U:
                answer += u * (u-1) // 2

            print(U)

        return answer


if __name__ == '__main__':

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

    # solve
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys

f = sys.stdin.readline()
x = f.split(' ')

n = int(x[0])
p = int(x[1])
p_len = len(str(x[1]))

s = sys.stdin.readline().replace('\n','')
count = 0
for i in range(0,len(s)):
  for j in range(i+p_len-1,len(s)):
    if( int(s[i:j+1:])%p == 0):
	count += 1

print count
sys.stdout.flush()

Submission status: Wrong Answer

Solution code:
n, p = (int(i) for i in input().split());

s = input();

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

h = [0 for i in range(len(s) + 1)];
st = 1;

for i in range(len(s) - 1,-1,-1):
    #print(i);
    h[i] = (st * int(s[i]) + h[i + 1]) % p;
    st = (st * 10) % p;

#print(h);

h.sort();

#print(h);

i = 0;
res = 0;

while i < n:
    j = i;
    while j + 1 < n and h[i] == h[j + 1]:
        j += 1;
    l = j - i + 1;
    res += (l * (l - 1)) // 2;
    i = j + 1;

print(res);

Submission status: Wrong Answer

Solution code:
n, p = (int(i) for i in input().split());

s = input();

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

h = [0 for i in range(len(s) + 1)];
st = 1;

for i in range(len(s) - 1,-1,-1):
    #print(i);
    h[i] = (st * h[i + 1] + int(s[i])) % p;
    st = (st * 10) % p;

#print(h);

h.sort();

#print(h);

i = 0;
res = 0;

while i < n:
    j = i;
    while j + 1 < n and h[i] == h[j + 1]:
        j += 1;
    l = j - i + 1;
    res += (l * (l - 1)) // 2;
    i = j + 1;

print(res);

Submission status: Wrong Answer

Solution code:
n, p = (int(i) for i in input().split());

s = input();

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

h = [0 for i in range(len(s) + 1)];
st = 1;

for i in range(len(s) - 1,-1,-1):
    #print(i);
    h[i] = (st * h[i + 1] + int(s[i])) % p;
    st = (st * 10) % p;

#print(h);

h.sort();

#print(h);

i = 0;
res = 0;

while i < n:
    j = i;
    while j + 1 < n and h[i] == h[j + 1]:
        j += 1;
    l = j - i + 1;
    res += (l * (l - 1)) // 2;
    i = j + 1;

print(res);

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  a=1
  for i in range(n)[::-1]:
     t+=int(s[i])*a
     t%=p
     a*=10
     a%=10
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  for i in range(n)[::-1]:
     t*=10
     t+=int(s[i])
     t%=p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  ss=""
  x2=0
  d={0:1}
  for i in range(n)[::-1]:
     ss+=s[i]
     t=int(ss)%p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     x1+=i+1 if int(s[i])%p==0 else 0
   print(x1)
else:
  ss=""
  x2=0
  d={0:1}
  for i in range(n):
     ss+=s[i]
     t=int(ss)%p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
from collections import Counter
[n,p]=i2()
s=input()
d=[]
ss=""
x1=0
for i in range(n):
  x1+=i+1 if int(s[i])%p==0 else 0
  ss+=s[i]
  d.append(int(ss)%p)
d.append(0)
c= Counter(d)
x2=0
for i in c.values():
  if i>1:
    x2+=i*(i-1)//2
if p==2 or p==5:
   print(x1)
else:
   print(x2)

Submission status: Wrong Answer

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
from collections import Counter
[n,p]=i2()
s=input()
d=[]
for i in range(n):
  d.append(int(s[i:])%p)
d.append(0)
c= Counter(d)
x=0
for i in c.values():
  if i>1:
    x+=i*(i-1)//2
print(x)

Submission status: Wrong Answer

Solution code:
n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    pass
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten *= 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)