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:
N,P = list(map(lambda x:int(x),input().split(" ")))
S = input()
count=0
store={}
if P in [2,5]:
  for i in range(N):
    if int(S[i])%P==0:
      count+=(i+1)
  print(count)
else:
  for i in range(N):
    num = int(S[i:])
    temp=num%P
    if temp in store:
      store[temp]+=1
    else:
      store[temp]=1
  for res,amm in store.items():
    if amm<2:
      continue
    count += amm*(amm-1)/2
  if 0 in store:
    count += store[0]
  #print(store)
  print(int(count))

Submission status: Time Limit Exceeded

Solution code:
N,P = list(map(lambda x:int(x),input().split(" ")))
S = input()
count=0
store=[0]*P
if P in [2,5]:
  for i in range(N):
    if int(S[i])%P==0:
      count+=(i+1)
  print(count)
else:
  for i in range(N):
    num = int(S[i:])
    store[num%P]+=1
  for i in range(P):
    count += store[i]*(store[i]-1)/2
  count += store[0]
  #print(store)
  print(int(count))

Submission status: Time Limit Exceeded

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 10 % P == 0:
        d = [0] * (P+1)
        s = 0

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

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

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



    print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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 10 % P == 0:
        d = [0] * (P+1)
        s = 0

        d[0] = 1
        for i in range(N):
            s += int(S[N-i-1]) * 10**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: Time Limit Exceeded

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
  b=pow(10,n-1)
  for i in range(n):
    a = a-int(s[i])*b
    r[a%p]+=1
    b=b//10
  #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: Time Limit Exceeded

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

m=0
l=input()
for i in range(n):

    if l[i] != 0:
        x=""
        
        for j in range(i,n):
            x +=l[j]
            if int(x) % p ==0:
                m += 1
print(m)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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-int(s[i])*pow(10,(n-1-i))
    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: Time Limit Exceeded

Solution code:
import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = []
  a = int(s)
  r.append(a%p)
  for i in range(n):
    a = a-int(s[i])*pow(10,(n-1-i))
    r.append(a%p)
  #print(r)
  r.sort()
  ans = 0
  cnt=1
  for i in range(len(r)-1):
    if r[i]==r[i+1]:
      cnt+=1
    else:
      ans +=cnt*(cnt-1)//2
      cnt=1
  print(ans+cnt*(cnt-1)//2)
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: Time Limit Exceeded

Solution code:
import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = []
  a = int(s)
  r.append(a%p)
  for i in range(n):
    a = a-int(s[i])*10**(n-1-i)
    r.append(a%p)
  #print(r)
  r.sort()
  ans = 0
  cnt=1
  for i in range(len(r)-1):
    if r[i]==r[i+1]:
      cnt+=1
    else:
      ans +=cnt*(cnt-1)//2
      cnt=1
  print(ans+cnt*(cnt-1)//2)
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: Time Limit Exceeded

Solution code:
import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = [0]
  for i in range(n):
    a = int(s[i:])%p
    r.append(a)
  #print(r)
  r.sort()
  ans = 0
  cnt=1
  for i in range(len(r)-1):
    if r[i]==r[i+1]:
      cnt+=1
    else:
      ans +=cnt*(cnt-1)//2
      cnt=1
  print(ans+cnt*(cnt-1)//2)
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: Time Limit Exceeded

Solution code:
import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and 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: Time Limit Exceeded

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

memo = {}
ans = 0

for i in range(N):
    for j in range(i + 1, N + 1):
        if S[i:j] in memo:
            ans += memo[S[i:j]]
        else:
            if int(S[i:j]) % P == 0:
                memo[S[i:j]] = 1
                ans += 1
            else:
                memo[S[i:j]] = 0

print(ans)

Submission status: Time Limit Exceeded

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

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

print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (int(s)*10**i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i += 1

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = [int(x) for x in input().split()]
S = input()

res = 0

if P in [2,5]:
    for i in range(N):
        if int(S[i])% P == 0:
            res += i+1
else:
    dic = {0:1}
    for i in range(N-1,-1,-1):
        tmp = int(S[i:N])
        t = tmp % P
        if t in dic:
            res += dic[t]
            dic[t] += 1
        else:
            dic[t] = 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
n,p =map(int,input().split())
s = list(input())
left = 0
right = 1
ans = 0
while left < n:
    while right <= n:
        num = int(("".join(s[left:right])))
        if num % p == 0:
            ans += 1
        right += 1
    left += 1
    right = left + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import time

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)
    
    # t3 = time.time()
    
    c = 0
    
    """
    for i in range(P):
        m = U.count(i)
        c += m*(m-1)//2
    print(c)
    """
    U.sort()
    # print(U)
    q = -1
    for i in range(N):
        if q != U[i]:
            q = U[i]
            m = U.count(q)
            c += m*(m-1)//2
    print(c)
    
    # t4 = time.time()
    # print(t4-t3)
    
    # 10032

Submission status: Time Limit Exceeded

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

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

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [defaultdict(int), defaultdict(int)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2

    dp[i1] = defaultdict(int)
    for j in dp[i0]:
        dp[i1][(j * 10 + s[i]) % p] += dp[i0][j]
    dp[i1][s[i] % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
s = input()

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [defaultdict(int), defaultdict(int)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2
    dp[i1] = defaultdict(int)
    for j in dp[i0]:
        dp[i1][(j * 10 + int(s[i])) % p] += dp[i0][j]
    dp[i1][int(s[i]) % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)

Submission status: Time Limit Exceeded

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

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [[0] * p for _ in range(2)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2
    dp[i1] = [0] * p
    for j in range(p):
        dp[i1][(j * 10 + int(s[i])) % p] += dp[i0][j]
    dp[i1][int(s[i]) % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (s*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
pre = 0
for s in S[::-1]:
  pre = MS(t,int(s),pre)
  M[pre] += 1
  t *= 10

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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 + i + 1
    print(ret)
else:
    c_list = [0] * n
    power = 1
    for i in range(len(s)):
        c_list[i] = (c_list[i-1] + (int(s[-i-1]) * power)) % p
        power *= 10
    c_list.append(0)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)

Submission status: Time Limit Exceeded

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


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 + i + 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)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)

Submission status: Time Limit Exceeded

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

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

M = [0]*p
pre = 0
ans = 0
i = 1
for s in S[::-1]:
  pre += int(s)*i
  pre %= p
  M[pre] += 1
  i *= 10

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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


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 + i + 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 + (cnt * (cnt - 1) // 2)
    print(ret)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
pre = 0
ans = 0
i = 1
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

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

def MS(i,s,pre):
  return (s*(10**i) +pre)%p
 
M = [0]*p
pre = 0
ans = 0
i = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i += 1

M[0] += 1
for m in M:
  ans += (m*(m-1))//2
print(ans)

Submission status: Time Limit Exceeded

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

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

M = [0]*p
pre = 0
ans = 0
i = 0
for s in S[::-1]:
  pre = (int(s)*(10**i) +pre)%p
  M[pre] += 1
  i += 1

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (s*(10**i) +pre)%p
 
M = [0]*p
pre = 0
ans = 0
i = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i += 1

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,s,pre):
  return (s*(10**i) +pre)%p
 
M = [0]*p
pre = 0
ans = 0
i = 0
for s in S[::-1]:
  M[MS(i,int(s),pre)] += 1
  pre = MS(i,int(s),pre)
  i += 1

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p = list(map(int,input().split()))
S = [int(s) for s in input()]

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if s%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*(10**i) +pre)%p
 
M = [0]*p
pre = 0
ans = 0
for i,s in enumerate(S[::-1]):
  M[MS(i,s,pre)] += 1
  pre = MS(i,s,pre)

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(i,si,pre):
  return (si*(10**i) +pre)%p
 
M = [0]*p
pre = 0
for i,s in enumerate(S[::-1]):
  M[MS(i,int(s),pre)] += 1
  pre = MS(i,int(s),pre)

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Submission status: Time Limit Exceeded

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

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

def MS(si):
  res = 0
  for i,s in enumerate(si):
    res += int(s)*(10**i)
  return res%p
  
  
s = [x for x in S]
M = [0]*p
for i,s in enumerate(S[::-1]):
  M[MS(S[::-1][:i+1])] += 1

M[0] += 1
ans = 0
for m in M:
  ans += (m*(m-1))//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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

if P == 2 or P == 5:
  tmp = ''
  ret = 0
  for i, s in enumerate(S):
    if int(s) % P == 0:
  	  ret += N - i
      
else:
  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: Time Limit Exceeded

Solution code:
N, P = input().split()
s = input()
cnt = 0
for i in range(1, 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: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input()
ans=0
for k in range(n):
  sbstr=""
  for i in range(k,n):
    sbstr+=s[i]
    if int(sbstr)%p==0:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input()
ans=0
for k in range(n):
  sbstr=""
  for i in range(k,n):
    sbstr+=s[i]
    if int(sbstr)%p==0:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input
N,P = map(int, input().split())
S = input()
# calculate
count = 0
for i in range(len(S)):
  for j in range(len(S)-i):
    S_temp = int(S[i:len(S)-j])
    if S_temp % P == 0:
      count += 1
# output
print(count)

Submission status: Time Limit Exceeded

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

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

S = list(map(int,[x for x in s]))
M = list(map(lambda x:x%p, S[::-1]))

MM = [0]*(n+1)
for i,m in enumerate(M):
    MM[i+1] = m*10**(i+1) + MM[i]

M = list(map(lambda x:x%p, MM))

ans = 0
U = set(M)

for u in U:
  cnt = M.count(u)
  ans += (cnt*(cnt-1))//2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:

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

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

S = list(map(int,[x for x in s]))
M = list(map(lambda x:x%p, S[::-1]))

MM = [0]*n
for i,m in enumerate(M):
  if i == 0:
    MM[i] = m
  else:
    MM[i] = m*10**(i) + MM[i-1]

M = list(map(lambda x:x%p, MM))

ans = 0
U = set(M)

for u in U:
  cnt = M.count(u)
  if u == 0:
    ans += (cnt*(cnt+1))//2
  else:
    ans += (cnt*(cnt-1))//2

print(int(ans))

Submission status: Time Limit Exceeded

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

res = 0

if p == 2 or p == 5:
  for i in range(n, 0, -1):
    if int(s[i-1])%p == 0:
      res += i
else:
  l = [0]*p
  l[0] = 1
  m = 0
  ten = 1
  for i in range(1, n+1):
    m += ten*int(s[-i])
    m %= p
    l[m] += 1
    ten *= 10%p

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

Submission status: Time Limit Exceeded

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

ret = 0
for left in range(N):
    for right in range(left,N):
        s = int(S[left:right+1])
        if s % P ==0:
            ret += 1
print(ret)

Submission status: Time Limit Exceeded

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

res = 0

if p == 2 or p == 5:
  for i in range(n, 0, -1):
    if int(s[i-1])%p == 0:
      res += i
else:
  l = [0]*p
  l[0] = 1
  m = 0
  ten = 1
  for i in range(1, n+1):
    m += ten*int(s[-i])
    l[m%p] += 1
    ten *= 10

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

Submission status: Time Limit Exceeded

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

res = 0

if p == 2 or p == 5:
  for i in range(n, 0, -1):
    if int(s[i-1])%p == 0:
      res += i
else:
  l = [0]*p
  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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    for j in range(i+1,N+1):
        n = int(S[i:j])
        if n % P == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

res = 0

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

        if crem == 0:
            res += 1
        res += dic_p[crem]

        dic_p[crem] += 1
        
else:
    for i,subs in enumerate(s[::-1]):
        if int(subs) % p == 0:
            res += n - i
    
print(res)

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

ans = 0
for i in range(n):
  v = 0
  for j in range(n-i):
    k1 = ls[i+j]
    v = v*10 + int(k1)
    m = v % p
    if m == 0 :
      ans += 1
    v = m
    
print(ans)

Submission status: Time Limit Exceeded

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

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

Solution code:
import sys

f = sys.stdin.readline()
xx = f.split(' ')
x = [int(str) for str in xx]

n = int(x[0])
p = int(x[1])

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

print count
sys.stdout.flush()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin 
from collections import defaultdict, Counter


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()

ans = 0 


# 2 cases
if P == 2 or P == 5:
	digitdiv = []
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1

else:
	#
	count = Counter()
	prefix = []
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1])*ten + mod) % P 
		prefix.append(x)
		count[x] += 1
		ten *= 10
		mod = x
	prefix.append(0)
	count[0] += 1
	for val in count.values():
		ans += val*(val - 1)//2


print (ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin 
from collections import defaultdict, Counter


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()

ans = 0 


# 2 cases
if P == 2 or P == 5:
	digitdiv = []
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1

else:
	#
	prefix = []
	for i in range(N):
		x = int(S[i:]) % P 
		prefix.append(x)
	prefix.append(0)
	count = Counter()
	for i in range(N + 1):
		count[int(prefix[i])] += 1

	for val in count.values():
		ans += val*(val - 1)//2


print (ans)

Submission status: Time Limit Exceeded

Solution code:
#E
NP = input().split(' ')
N = int(NP[0])
P = int(NP[1])
S = int(input())
S_list = list(str(S))
count = 0

for m in range(N):
    ques = int(S_list[m])
    if ques % P == 0:
        count += 1
    for k in range(m+1, N):
        ques = ques*10 + int(S_list[k])
        if ques % P == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin 
from collections import defaultdict 


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()


tens_mod = []
count = 1
for i in range(N - 1):
	count *= 10 % P 
	tens_mod.append(count)

ans = 0
# dp: length/right pos index
dp = defaultdict(lambda:[0]*N)
for i in range(N):
	x = int(S[i])
	dp[1][i] = x % P
	if x % P == 0:
		ans += 1

# length of segment
for i in range(2, N + 1):
	# right pos index 
	for j in range(i - 1, N):
		x = (dp[i - 1][j - 1]*10 + dp[1][j]) % P
		if x == 0:
			ans += 1
		dp[i][j] = x

print (ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(n):
    for j in range(1,n-i+1):
        if int(s[i:i+j])%p == 0:
            cnt +=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
r = input().split()
n = int(r[0])
p = int(r[1])
s = input()
count = 0

for i in range(n):
    for j in range(i+1, n+1):
        #print(i,j)
        sub = s[i:j]
        #print(sub)
        if int(sub) % p == 0:
            count += 1
print(count)