TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

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


else:
    dp1 = np.zeros(N + 1)
    dp2 = np.zeros(N + 1)
    dp3 = np.zeros(P)
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(dp1)
    print(dp3)
    print(int(sum))


# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

dp1 = np.zeros(N+1)
dp2 = np.zeros(N+1)
dp3 = np.zeros(P)
zero_count = 0
dp1[N] = int(S[N]) % P
dp3[int(dp1[N])] += 1
k = 1
for i in range(N-1, 0, -1):
    dp1[i] = (dp1[i+1] + ((int(S[i]) * 10 * k) % P)) % P
    dp3[int(dp1[i])] += 1
    k = (k * 10) % P
    if int(S[i]) % P == 0:
        zero_count += 1

sum = 0
for i in range(P):
    if i == 0:
        sum += (dp3[i] * dp3[i] - 1) // 2 + dp3[i]
        continue
    sum += (dp3[i] * dp3[i] - 1) // 2

print(int(sum)-zero_count)

# coding: utf-8

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

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

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


else:
    dp1 = [0] * (N+1)
    dp2 = [0] * (N+1)
    dp3 = [0] * P
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(int(sum))


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n, p = map(int, input().split(' '))
s = input()
p_len = len(str(p))
ans = 0

for i in range(len(s), len(s) + 1 - p_len):
    for j in range(i + p_len, len(s) + 1):
        n_ss = int(s[i:j])
        if n_ss % p == 0:
            ans += 1

print(ans)

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)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import Counter
import sys
if sys.platform == 'ios' or 'darwin':
    sys.stdin = open('input_file.txt')

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]) % 2 == 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)

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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from collections import Counter
N, P = map(int, input().split())
S = input()

if 10 % P == 0:
    ans = 0
    for i, s in enumerate(S, start=1):
        if int(s) % P != 0:
            continue
        ans += i
    print(ans)

else:
    X = [0]
    for i, s in enumerate(S[::-1]):
        X.append((X[-1] + pow(10, i, P) * int(s)) % P)

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


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

if 10 % P == 0:
    ans = 0
    for i, s in enumerate(S, start=1):
        if int(s) % P != 0:
            continue
        ans += i
    print(ans)

else:
    X = [0]
    for i, s in enumerate(S[::-1]):
        X.append((X[-1] + pow(10, i, P) * int(s)) % P)

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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys

n,p = list(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)
    sys.exit()
    
res = [0] * p
arr = [int(s[i:])%p for i in range(n)]
for i in arr:
    res[i] += 1
for i in res:
    ans += i*(i-1)
    ans //= 2
ans += res[0]
    
print(ans)

n,p = list(map(int,input().split())); s = [int(i) for i in input()]

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p == 0:
            ans += i+1
    print(ans)
    
else:
    s = s[::-1]
    res = [0] * p
    arr = [0] * n
    tmp = 0
    for i in range(n):
        tmp += s[i]*pow(10,i,p)
        tmp %= p
        arr[i] = tmp
    for i in arr:
        res[i] += 1
    for i in res:
        ans += i*(i-1)
    ans //= 2
    ans += res[0]
        
    print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import Counter

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

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

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)


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

print(ans)


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)


# ans += counter[0]
# print(ans)

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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
  n, p = map(int, input().split())
  s = input()


  def solve1(s, p):
      v = 0
      pow10 = 1
      ans = 0
      cnt = [0] * p
      cnt[0] = 1

      for i in range(n - 1, -1, -1):
          v = (pow10 * int(s[i]) + v) % p
          pow10 = (pow10 * 10) % p
          ans += cnt[v]
          cnt[v] += 1
      return ans


  def solve25(s, p):
      cnt = 0
      ans = 0
      for i in range(len(s) - 1, -1, -1):
          if int(s[i]) % p == 0:
              cnt += 1
          ans += cnt
      return ans



  if p in (2,5):
      print(solve25(s, p))
  else:
      print(solve1(s, p))

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


def solve1(s, p):
    v = 0
    pow10 = 1
    ans = 0
    cnt = [0] * p
    cnt[0] = 1

    for i in range(n - 1, -1, -1):
        v = (pow10 * int(s[i]) + v) % p
        pow10 = (pow10 * 10) % p
        ans += cnt[v]
        cnt[v] += 1
    return ans


def solve25(s, p):
    cnt = 0
    ans = 0
    for i in range(len(s) - 1, -1, -1):
        if int(s[i]) % p == 0:
            cnt += 1
        ans += cnt
    return ans



if p in (2,5):
    print(solve25(s, p))
else:
    print(solve1(s, p))


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from collections import Counter

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

s = input()


a = 0
t = list(map(int, list(s)))
t.reverse()


if p == 2:
    for i in range(n):
        if t[i] % 2 == 0:
            a += len(t) - i 
elif p == 5:
    for i in range(n):
        if t[i] % 5 == 0:
            a += len(t) - i 

else:
    u = []
    k = 1
    for i in t:
        l = 0
        if i == 0:
            l = i*k % p
            u.append(k)
        else:
            l = (l + i*k) % p
            u.append(l)
        k = k * 10 % p

    c = Counter(u)
    a += c[0]
    for i in c.values():
        if i > 1:
            a += i * (i-1) // 2


print(a)




from collections import Counter

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

s = input()


a = 0
t = list(map(int, list(s)))
t.reverse()


if p == 2:
    for i in range(n):
        if t[i] % 2 == 0:
            a += len(t) - i 
elif p == 5:
    for i in range(n):
        if t[i] % 5 == 0:
            a += len(t) - i 

else:
    u = []
    k = 1
    l = 0
    for i in t:
        l = (l + i*k) % p
        u.append(l)
        k = k * 10 % p

    c = Counter(u)
    a += c[0]
    for i in c.values():
        if i > 1:
            a += i * (i-1) // 2


print(a)




Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
#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]
    for i in range(n):
        x=n-1-i
        U.append((U[i]+int(s[x])*10**(i))%p)
    print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

#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])*10**(n-i)+U[i])%p
    print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

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

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

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

n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np

def a():
  n, p = list(map(int, input().split()))
  s = input()
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(int(s[-i])%p == 0):
        count += n-i+1
    print(count)
    return

  num = np.array([int(s[i:]) for i in range(n)]) % p
  print(num)
  c = sum(num == 0)
  count = c*(c+1)//2
  for i in range(1,p):
    c = sum(num == i)
    count += c*(c-1)//2
  print(count)
  return
a()

import numpy as np

def a():
  n, p = list(map(int, input().split()))
  s = input()
  if(p==2 or p==5):
    print("im here")
    count=0
    for i in range(1,n+1):
      if(int(s[-i])%p == 0):
        count += n-i+1
    print(count)
    return

  num = np.array([int(s[i:]) for i in range(n)]) % p
  print(num)
  c = sum(num == 0)
  count = c*(c+1)//2
  for i in range(1,p):
    c = sum(num == i)
    count += c*(c-1)//2
  print(count)
  return
a()

import numpy as np

def a():
  n, p = list(map(int, input().split()))
  num = [int(s) for s in input()]
  
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(num[-i]%p == 0):
        count += n-i+1
    print(count)
    return
  
  counts = np.zeros(p)
  tmp = 0
  tens = 1
  for i in range(1,n+1):
    tmp = (tens*num[-i] + tmp) % p
    counts[tmp] += 1
    tens = (tens*10)%p
  ret = int(counts[0] + sum(counts*(counts-1)//2))
  print(ret)
  return
a()

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N,P=map(int,input().split())
S=str(input())
ans=0

if 10%P==0:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
else:
    rem = [0]*P
    mod = 0
    ten = 1
    rem[mod]=1
    for i in range(N):
        mod=(mod+S[N-i-1]*ten)%P
        ten=ten*10%P
        rem[mod]+=1
    for j in rem:
        ans+=(j*(j-1))//2
print(ans)

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

if 10%P==0:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
else:
    rem = [0]*P
    mod = 0
    ten = 1
    rem[mod]=1
    for i in range(N):
        mod=(mod+int(S[N-i-1])*ten)%P
        ten=ten*10%P
        rem[mod]+=1
    for j in rem:
        ans+=(j*(j-1))//2
print(ans)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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(s) * pow(10, i, p) + now) % p
        ans += cnt[now]
        cnt[now] += 1

print(ans)

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)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s 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)
        return

    
    L = [0]*P
    L[0] = 1
    t = 0
    for i in range(N):
        t = (S[i]*pow(10,i,P)+t)%P
        print(t)
        L[t] += 1
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()


def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s 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)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s *= 10
        s %= 10
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()


import sys
input = sys.stdin.readline
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s 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)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()


def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input().strip())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for z in S:
        t = (z*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N, P = map(int, input().split())
d = list(map(int, input()))
ans =0
for k in range(0,N):
    for l in range(k+1,N+1):
        num = int("".join(map(str,d[k:l])))
        
        if num == 0:
            break
        elif num % P == 0:
            ans += 1
            print(num)

print(ans)


N, P = map(int, input().split())
S = list(map(int, input()))
ans = 0
if P == 2:
    for i in range(N):
        if S[i]%2 == 0:
            ans +=i+1
    print(ans)

elif P ==5:
    for i in range(N):
        if S[i]%5 == 0:
            ans +=i+1
    print(ans)
else:
    data =[0]*P
    tens = 1
    k = 0
    for i in range(N-1,-1,-1):
        k += S[i] *tens %P
        k = k%P
        data[k] += 1
        tens *=10
        tens %=P

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

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
dp = [[0 for i in range(N-j)] for j in range(N)]
dp
for j in range(N):
    dp[j][0]=(int(S[j])%mod)
    for i in range(1,N-j):
        dp[j][i]=((dp[j][i-1]*10+int(S[j+i]))%mod)
ans = 0
for i in range(N):
    ans += dp[i].count(0)
    
print(ans)

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)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N,P = map(int,input().split())
S = list(map(int,list(input())))
S=S[::-1]
ans = 0
from collections import Counter
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]*(N+2)
  for i in range(N):
    l[i+1]=l[i]
    l[i+1]+=(S[i]*10**i)%P
    l[i+1]%=P
    
  c = Counter(l)
  l = list(c.values())
  l = sorted(l)
  for i in l:
    if l==1:
      continue
    else:
      ans+=c*(c-1)//2
      
print(ans)

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
print(ans)

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

N,P = map(int,input().split())
S = list(map(int,list(input())))
S=S[::-1]
ans = 0
from collections import Counter
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]*(N+2)
  for i in range(N):
    l[i+1]=l[i]
    l[i+1]+=(S[i]*10**i)%P
    l[i+1]%=P
    
  c = Counter(l)
  l = list(c.values())
  l = sorted(l)
  for i in l:
    if l==1:
      continue
    else:
      ans+=i*(i-1)//2
      
print(ans)

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

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

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
def main():
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    else #if P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    """
    A = [int(s) for s in S]
    from itertools import accumulate
    acc = accumulate([0] + A)
    right = N
    for left in range(N):
        while left

    print()
    """
    print(ans)


if __name__ == '__main__':
    main()


def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # 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()


Verdicts: Runtime Error

Accepted
Problem: 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.

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

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

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

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)


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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from collections import defaultdict

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

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())  

from collections import defaultdict

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

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)%P]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())  

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import sys

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


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


def main():
    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
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= 10
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()


import sys

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


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


def main():
    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
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n,p=map(int,input().split())
s=[int(j) for j in input()][::-1]

if p==2:
    ans=0
    for i,j in enumerate(s):
        if j%2==0:
            ans+=(n-i)
    print(ans)
    exit()
if p==5:
    ans=0
    for i,j in enumerate(s):
        if j%5==0:
            ans+=(n-i)
    print(ans)
    exit()

c=[0]*p
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    print(tmp)
    c[tmp%p]+=1
    t=(t*10)%p
c=np.array(c)
print(c)
ans=c*(c-1)//2
print(ans.sum())


n,p=map(int,input().split())
s=[int(j) for j in input()][::-1]

if p==2:
    ans=0
    for i,j in enumerate(s):
        if j%2==0:
            ans+=(n-i)
    print(ans)
    exit()
if p==5:
    ans=0
    for i,j in enumerate(s):
        if j%5==0:
            ans+=(n-i)
    print(ans)
    exit()

c=[0]*p
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%p]+=1
    t=(t*10)%p
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    if p==2 or p==5:
        ans=0
        for i,c in enumerate(s):
            if int(c)%p==0:ans+=i+1
        print(ans)
        exit()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    print(cc)
    print(cnt)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
        print(v,ans)
    print(ans)

main()

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    if p==2 or p==5:
        ans=0
        for i,c in enumerate(s):
            if int(c)%p==0:ans+=i+1
        print(ans)
        exit()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
    print(ans)

main()

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n, p = map(int, input().split())
 
s = list(input())
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        sum+=a
        ten *= 10
        ten %= p
        d[i]= sum % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2
print(d)
print(int(ans))

n, p = map(int, input().split())
 
s = list(input())
ans = 0
sum=0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        sum+=a
        ten *= 10
        ten %= p
        d[i]= sum % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2
print(d)
print(int(ans))

n, p = map(int, input().split())
 
s = list(input())
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        ten *= 10
        ten %= p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2

print(int(ans))

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
# from collections import Counter
n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(n):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    print(div_dic)
    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)

n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
        
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(n):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N,P = map(int,input().split())
S = input()

if P%2 == 0 or P%5 == 0:
    ans = 0
    S = S[::-1]
    for i,j in enumerate(S):
        if int(j)%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    ##mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

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

if P%2 == 0 or P%5 == 0:
    ans = 0
    ##S = S[::-1]
    for i,j in enumerate(S):
        if int(j)%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

Verdicts: Wrong Answer

Accepted