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: Time Limit Exceeded

Solution code:
from collections import deque

dic = {}

def dic_add( an ):
  cnt = dic.get(an)
  if cnt is None:
    dic[an] = 1
  else:
    dic[an] = cnt + 1

def ifcnt( an, ap ):
  if an % ap == 0 :
    return 1
  else:
    return 0

s = input().split()
n = int(s[0])
p = int(s[1])

ls = input()

#print(n,p)
ans = 0
for i in range(n):
  v = 0
  for j in range(n-i):
    v = v*10 + int(ls[i+j])
    #print(v)
    dic_add(v)
    #ans += ifcnt( v , p )
    #
    ##print('{}:{}'.format(v,ans) )
#print('-----')
for e in dic:
  ans = ans + ifcnt( e , p ) * dic[e]
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def ifcnt( an, ap ):
  if an % ap == 0 :
    return 1
  else:
    return 0

s = input().split()
n = int(s[0])
p = int(s[1])

ls = input()

#print(n,p)
ans = 0
for i in range(n):
  v = 0
  for j in range(n-i):
    v = v*10 + int(ls[i+j])
    #print(v)
    ans += ifcnt( v , p )
    #print('{}:{}'.format(v,ans) )
#print('-----')
print(ans)

Submission status: Time Limit Exceeded

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]
  a=1
  for i in range(n)[::-1]:
     t+=int(s[i])*a
     t%=p
     a*=10
     d.append(t)
  from collections import Counter
  c= Counter(d)
  x=0
  for i in c.values():
    if i>1:
      x+=i*(i-1)//2
  print(x)

Submission status: Time Limit Exceeded

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
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

Submission status: Time Limit Exceeded

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+=int(s[i])*10**(n-1-i)
     t%=p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

Submission status: Time Limit Exceeded

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


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
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 = ten * 10
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

Submission status: Time Limit Exceeded

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


if 10 % p == 0:
    out = 0
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
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)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

if 10%p==0:
    ans = 0
    for r in range(n):
        if int(s[r])%p == 0:
            ans += r+1
    print(ans)
    exit()

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

Submission status: Time Limit Exceeded

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

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

tmp = [0] * p
tmp[0] = 1
mod = 0
for i in range(1,n+1):
    mod += (int(s[-i]) * 10**i) % p
    mod %= p
    tmp[mod] += 1

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

print(ans)

Submission status: Time Limit Exceeded

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

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

tmp = [0] * p
tmp[0] = 1
mod = 0
for i in range(1,n+1):
    mod += (int(s[-i]) * 10**i) % p
    mod %= p
    ans += tmp[mod]
    tmp[mod] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

"""
S = "s0 s1 ... s(N-1)"に対して"sl s(l+1) ... s(r-1)"が素数Pで割り切れるかを考える。
これはa_i := int("si s(i+1) ... s(N-1)")と定めることで、
    (a_l - a_r) / 10^{N-r} ¥cong 0  (mod P)
と定式化できる。

（整数関連の区間の問題は後ろからの累積和が相性良さそう。頭からの累積を考えたのが敗因な気がする）

Pが2でも5でもない場合は、上式は
    a_l - a_r ¥cong 0 (mod P)
に同値であるから、各a_iのmod Pでの値を辞書にまとめておけば良さそう。
Pが2, 5のいずれかの場合は偶然チェックが簡単なので解ける。
"""

ans = 0
if P == 2:
    for i in range(N):
        a = int(S[i])
        if a % 2 == 0:
            ans += i + 1
elif P == 5:
    for i in range(N):
        a = int(S[i])
        if a == 0 or a == 5:
            ans += i + 1
else:
    S += "0" # 上の定式化の都合上、r = Nのケースが必要なので
    res = [0] * P
    for i in range(N + 1):
        a = int(S[i:]) % P
        res[a] += 1

    for r in res:
        ans += r * (r - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

"""
S = "s0 s1 ... s(N-1)"に対して"sl s(l+1) ... s(r-1)"が素数Pで割り切れるかを考える。
これはa_i := int("si s(i+1) ... s(N-1)")と定めることで、
    (a_l - a_r) / 10^{N-r} ¥cong 0  (mod P)
と定式化できる。

（整数関連の区間の問題は後ろからの累積和が相性良さそう。頭からの累積を考えたのが敗因な気がする）

Pが2でも5でもない場合は、上式は
    a_l - a_r ¥cong 0 (mod P)
に同値であるから、各a_iのmod Pでの値を辞書にまとめておけば良さそう。
Pが2, 5のいずれかの場合は偶然チェックが簡単なので解ける。
"""

ans = 0
if P == 2:
    for i in range(N):
        a = int(S[i])
        if a % 2 == 0:
            ans += i + 1
elif P == 5:
    for i in range(N):
        a = int(S[i])
        if a == 0 or a == 5:
            ans += i + 1
else:
    S += "0" # 上の定式化の都合上、r = Nのケースが必要なので
    d = defaultdict(int)
    for i in range(N + 1):
        a = int(S[i:]) % P
        d[a] += 1

    for res in d:
        ans += d[res] * (d[res] - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

if P in (2, 5):
    count = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            count += i + 1
    print(count)
else:
    d = defaultdict(int)
    r = 0
    for i in range(N):
        r += int(S[N - 1 - i]) * 10 ** (i % (P - 1))
        r %= P
        d[r] += 1

    count = d[0]
    for num in d.values():
        count += num * (num - 1) // 2
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

if P in (2, 5):
    count = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            count += i + 1
    print(count)
else:
    d = defaultdict(int)
    r = 0
    for i in range(N):
        r = (r + int(S[N - 1 - i]) * 10 ** i) % P
        d[r] += 1

    count = d[0]
    for num in d.values():
        count += num * (num - 1) // 2
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = list(map(lambda x:int(x),input().split()))
s = input()
count=0

if P==5:
  for i in range(N):
    if s[i] in ["5","0"]:
      count+=(i+1)
elif P==2:
  for i in range(N):
    if s[i] in ["2","4","6","8","0"]:
      count+=(i+1)
else:
  store= [0]*P
  #idx=[]
  for i in range(N):
    u = (int(s[i:]))%P
    store[u] +=1
  for i in range(P):
    #print(i,count)
    count += store[i]*(store[i]-1)/2

  count += store[0]
#print(store)
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
n,p = tuple(map(int,input().split()))
s = input()
modulo = [0]*p
modulo[0] = 1
if p!= 2 and p != 5:
    for i in range(n):
        modulo[int(s[i:]) % p] += 1

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

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

Submission status: Time Limit Exceeded

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

a = [0] * n

for i in range(n):
  m = (int(s[i])*10**i)%p
  if i==0:
    a[i] = m
  else:
  	a[i] = (m + a[i-1])%p
  #print(s[i], p, m, a[i])

import collections
ans = 0
if p%2==0 or p%5==0:
  for i in range(n):
    if int(s[i])%p==0:
      ans += n-i
else:
  c = collections.Counter(a)
  for k in c:
    cnt = c[k]
    if k==0:
      ans += (cnt*(cnt+1))//2
    else:
      ans += (cnt*(cnt-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3 ## -*- python -*-
t = input().split()
n = int(t[0])
p = int(t[1])
s = input()

# 文字列sから長さlの文字列を生成する。開始位置をずらして複数生成する。割り切れる数をかえす。
def mkstr(l):
    c = 0
    for i in range(n+1-l):
        if int(s[i:i+l]) % p == 0:
            c = c+1
    return c

c = 0
for i in range(n):
    c += mkstr(i+1)

print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3 ## -*- python -*-
t = input().split()
n = int(t[0])
p = int(t[1])
s = input()

# 文字列sから長さlの文字列を生成する。開始位置をずらして複数生成する。
def mkstr(l):
    st = []
    for i in range(n+1-l):
        st.append(s[i:i+l])
    return st

c = 0
for i in range(n):
    for w in mkstr(i+1):
        if int(w) % p == 0:
            c = c+1

print(c)

Submission status: Time Limit Exceeded

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:
	t = [0] * 20000
	t[0] = 1
	now = 0
	for i in range(N):
		n = N - i - 1
		now = (int(S[n]) * pow(10,i) + now) % P
		ans += t[now]
		t[now] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


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

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


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        if not (a in nums):
            nums[a] = 1
        else:
            nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=input()
if P==2 or P==5:
    ans=0
    for i in range(len(S)):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)            
else:
    L=[0]
    for i in enumerate(S[::-1]):
        i0=int(i[0])
        i1=int(i[1])
        L.append((10**i0%P * i1 + L[-1])%P)
    L.pop(0)    
    sl=set(L)
    ans=L.count(0)
    for i in sl:
        cnt = L.count(i)
        ans += cnt*(cnt-1)//2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


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

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


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        nums[a] = 0
    for a in A:
        nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys

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

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


ans = 0
if P==2 or P==5:
    for i in reversed(range(N)):
        if int(S[i])%P==0:
            ans += i+1
else:
    nums = {}
    for a in A:
        nums[a] = 0
    for a in A:
        nums[a] += 1
    
    for n in nums.keys():
        k = nums[n]
        if n==0:
            ans += k*(k+1)//2
        else:
            ans += k*(k-1)//2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:

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

Submission status: Time Limit Exceeded

Solution code:

def Cf(n):
    if n == 1 or n ==0:
        return 0
    else:
        return n*(n-1)//2



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
    S[-1] = S[-1]%P
    data[S[-1]] +=1
    for i in range(N-2,-1,-1):
        k = (S[i+1] + S[i]*(10**(N-i-1))) %P
        S[i] =k
        data[k] += 1
    for i in data:
        ans += Cf(i)
    ans +=data[0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

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



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:
    S[-1] = S[-1]%P
    for i in range(N-2,-1,-1):
        S[i] = (S[i+1] + S[i]*(10**(N-i-1))) %P
    S.sort()
    cnt = 1
    for i in range(N-1):
        if S[i] == S[i+1]:
            cnt +=1
        else:
            ans += Cf(cnt)
            cnt =1
        if S[i] ==0:
            ans+=1
    if S[-1] == 0:
        ans +=1
    if cnt >1:
        ans += Cf(cnt)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b = [int(x) for x in input().split()]
s = input()
sl = list(s)
c = ""
count = 0
for i in range(a):
  for x in range(i,a):
    c = c + sl[x]#iが0ならsl[0],sl[0]+sl[1],sl[0]++sl[a-1]
    if int(c) % b == 0:
      count = count + 1
  c = ""
print(count)

Submission status: Time Limit Exceeded

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

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * pow(10 ** (N - 1 - i), P)
        tmp %= P
        ans += count[tmp]
        count[tmp] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

Submission status: Time Limit Exceeded

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

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * 10 ** (N - 1 - i)
        tmp %= P
        ans += count[tmp]
        count[tmp] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

Submission status: Time Limit Exceeded

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

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * 10 ** (N - 1 - i)
        tmp %= P
        ans += count[tmp]
        count[tmp % P] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

Submission status: Time Limit Exceeded

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

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * 10 ** (N - 1 - i)
        ans += count[tmp % P]
        count[tmp % P] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

total = 1 if int(S[0]) % P == 0 else 0
amari = [[0] * P for _ in range(2)]
amari[0][int(S[0]) % P] = 1
for i in range(1, N):
    for j in range(P):
        amari[i%2][j] = 0
    for j in range(P):
        if amari[(i+1)%2][j] > 0:
            amari[i%2][(j * 10 + int(S[i])) % P] += amari[(i+1)%2][j]
    amari[i%2][int(S[i]) % P] += 1
    total += amari[i%2][0]
    
print(total)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=list(input())
S=S[::-1]
Si=[0]*N
cnt=0
sum=0
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            cnt+=N-i

else:
    mod=[(int(k)*10**j)%P for j,k in enumerate(S)]
    for m,n in enumerate(mod):
        sum+=n
        Si[m]=sum%P
    
    cnt+=Si.count(0)
    for i in range(P):
        num_i=Si.count(i)
        cnt+=num_i*(num_i-1)/2
        
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=str(input())
S=S[::-1]
Si=[]
count=0
sum=0
if P==2:
    for i in range(N):
        if int(S[i])%2==0:
            count+=N-i
elif P==5:
    for i in range(N):
        if S[i]=="0" or S[i]=="5":
            count+=N-i
else:
    listS=[int(i) for i in S]
    mod=[(k*10**j)%P for j,k in enumerate(listS)]
    for m in mod:
        sum+=m
        Si.append(sum%P)
        
    for start in range(N):
        if Si[start]==0:
            count+=1            
        for end in range(start+1,N):
            if Si[start]==Si[end]:
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
a = input().split(" ")
a[1] = int(a[1])
num = input()
count = 0
for i in range(int(a[0])):
    for j in range(int(a[0]) - i):
        s = num[i:(i+j+1)]
        if(int(s) % a[1] == 0):
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

listS=[i for i in S]


for start in range(N):
    for end in range(start,N):
        num=""
        for i in range(start,end+1):
            num=num+listS[i]       
        num=int(num)
        if num%P==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

listS=[int(i) for i in S]
for start in range(N):
    for end in range(start,N):
        num=0
        for i in range(start,end+1):
            num+=listS[i]*(10**(end-i))   
        if num%P==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().rstrip().split()]
S = input()
R = 0
if P in [2,5]:
    for i,s in enumerate(S):
        if int(s) % P == 0:
            R += i+1
else:
    I = [int(S[i:])%P for i in range(len(S))] + [0]
    I = [sum([(I[i] - j)%P == 0 for j in I[i+1:]]) for i in range(len(S))]
    R = sum(I)
print(R)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * (10 ** i)
        mods[num % P] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        c = num % P
        cnt += mods[c] - 1
        mods[c] -= 1
        num -= int(s) * (10 ** (N - 1 - i))

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

cnt = 0
if P in [2, 5]:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            cnt += (i + 1)
else:
    num = 0
    mods = Counter()
    for i, s in enumerate(reversed(S)):
        num += int(s) * (10 ** i)
        mods[num % P] += 1
    mods[0] += 1
    for i, s in enumerate(S):
        c = num % P
        cnt += mods[c] - 1
        mods[c] -= 1
        num -= int(s) * (10 ** (N - 1 - i))

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
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)
    for i in range(n - 1, -1, -1):
        a = (int(s[i]) * 10 ** ((n - 1) - i)) % p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        ans += cnt[d[i]]
        cnt[d[i]] += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
d = list(map(int, input())) + [0]
ans =0
for k in range(0,N):
    num = [d[k]]
    for l in range(k+1,N+1):
        nu = int("".join(map(str,num)))
        if nu % P == 0:
            ans += 1
        num.append(d[l])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 % P == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
num = 0
for i in range(n):
  m = 0
  for j in range(i, n):
    m = (10*m + int(s[j])) % p
    if(m == 0):
      count += 1
    
print(count)

Submission status: Time Limit Exceeded

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

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    tenPow = 1
    for i in range(N):
        num = (num + S[N-i-1]*tenPow)%P
        tenPow *= 10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

# output
print(ans)

Submission status: Time Limit Exceeded

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

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    for i in range(N):
        num += S[N-i-1]*10**i
        cnt[num%P] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

# output
print(ans)

Submission status: Time Limit Exceeded

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

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    S = list(map(int, S))
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    for i in range(N):
        cnt[int(S[i:N])%P] += 1

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

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque
# d = deque()
import itertools


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

count = 0

1

for s, e in itertools.combinations(range(N+1), 2):
    num = S[s:e]
    num = int(num)
    if num%P == 0:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque
# d = deque()
import itertools


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

count = 0

for s in range(N):
    for e in range(s+1, N+1):
        num = S[s:e]
        num = int(num)
        if num%P == 0:
            count+=1

print(count)

Submission status: Time Limit Exceeded

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

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

    l = {0:1}
    s1 = s[::-1]

    mod = 0
    for i in range(n):
        mod += int(s1[i])*10**i%p
        mod %= p
        if mod in l:
            l[mod] += 1
        else:
            l[mod] = 1
    ans = 0

    for i in l.values():
        ans += (i-1)*i//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

l = [0]

s1 = s[::-1]
l.append(int(s1[0])%p)
for i in range(1,n):
    check = int(s1[i])*10**i%p
    l.append((l[-1]+check)%p)
ans = 0

for i in range(p):
    k = l.count(i)*(l.count(i)-1)//2
    ans += k
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

# process
sl = [] # S[i:N]のリスト
for i in range(N):
    sl.append(int(S[i:N]))
sl.append(0)

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        if (sl[i]-sl[j])//10**(N-j)%P == 0:
            ans += 1

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n, p = map(int,input().split())
D = input()
s = [0] * n
mod = 0
out = 0
if 10 % p == 0:
    for i, d in enumerate(D):
        if int(d) % p == 0:
            out += i + 1
else:
    D = D[::-1]
    M = [(int(d) * 10 ** i) % p for i, d in enumerate(D)]
    s[0] = M[0]
    for i in range(1, n):
        s[i] = (s[i - 1] + M[i]) % p
    C = collections.Counter(s)
    out += C[0]
    for c in C.values():
        out += (int(c) * (int(c) - 1)) / 2
print(int(out))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import sys
a = input().split()
N = int(a[0])
P = int(a[1])
S = input()
count = 0
num = 0
for i in range(N):
    for j in range(N-1,-1,-1):
        k = j - i + 1
        if(k>0):
            num = 0
            for l in range(i, j+1):
                num = num + int(S[l]) * (10**(k-l+i-1))
                if num % P == 0 and l==j:
                    count = count + 1
print(count)

Submission status: Time Limit Exceeded

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

a=[0]*(N+1)

if P!=2 and P!=5:
    for i in range(N):
        a[i] = int(S[i:])%P
    ans=0
    from collections import Counter
    C=Counter(a)
    for k,v in C.items():
        ans+=v*(v-1)//2
elif P==2:
    ans=0
    for i in range(N):
        if int(S[i])%2==0:
            ans+=i+1
elif P==5:
    ans=0
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            ans+=i+1

print(ans)

Submission status: Time Limit Exceeded

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

a = [0] * (N + 1)
r = [0] * (N+1)

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = (int(S[N-i])*tenfactor+a[i-1])
        tenfactor*=10
        r[i]=a[i]%P

    ans = 0
    from collections import Counter
    C=Counter(r)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)