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

mod_10=10%p

#余りがkとなる組み合わせの数の配列

answer=0

dp=[0 for i in range(p)]
dp2=[0 for i in range(p)]
st=int(s[0])%p
dp[st]+=1
use_set={st}
answer+=dp[0]

for i in range(1,n):
    tmp_set=set()
    mod_i = int(s[i])%p
    tmp_set.add(mod_i)
    dp2[mod_i]+=1
    for num in use_set:
        tmp_num=(mod_i+mod_10*num)%p
        tmp_set.add(tmp_num)
        dp2[tmp_num]+=dp[num]
        dp[num]=0
    
    dp,dp2 = dp2,dp
    tmp_set, use_set = use_set,tmp_set
    answer+=dp[0]  

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input()
tenlist=[1]
for i in range(1,n):
    tenlist.append((tenlist[i-1]*10)%p)
count=0
for i in range(n):
    num=int(s[i])%p
    if num==0:
        count+=1
    for j in range(i):
        num=(num+int(s[i-j-1])*tenlist[j+1])%p
        if num==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
res = 0
for i in range(n):
    ss = ""
    mod = 0
    for j in range(i, n):
        ss = ss + s[j]
        mod *= 10
        mod += int(s[j]) % p
        mod %= p
        #print(ss)
        #print("ss", int(ss) % p, mod)
        if int(ss) % p == 0:
            res += 1
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0
for left in range(L_S):
    for right in range(left + 1, L_S + 1):
        num = S[left:right]
        while num[0] == '0' and len(num) > 1:
            num = num[1:]
        if (int(num) % P) == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def countSubStr(str, l, k): 
	count = 0
	for i in range(l): 
		n = 0 
		for j in range(i, l, 1): 
			n = n * 10 + (ord(str[j]) - ord('0')) 
			if (n % k == 0): 
				count += 1	
	return count 

if __name__ == '__main__': 
    n, p = list(map(int, input().split()))
    s = input()
    n = len(s) 
    k = 11
    print(countSubStr(s, n, p))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

st = 0
en = 1
cnt = 0

while(st < N):
    num = int(S[st:en])
    if num//P>0 and num%P ==0 or num == 0:
        cnt += 1
    if en < N:
        en += 1
    else:
        st += 1
        en = st + 1

print(cnt)

Submission status: Time Limit Exceeded

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

result = 0
tc = [0] * n
tims = []
pl = len(str(p))
for k in range(len(s)):
    i = s[k]
    total = i
    tims.append(i)
    if pl > len(tims):
        continue
    total = 0
    for j in range(len(tims))[::-1]:
        total = total * 10
        total += tims[j]
        if total % p == 0:
            result +=1
            tca = k - (len(tims)-1-j)
            tci = 0
            if tca != 0:
                tci = tc[tca-1]
            result += tci
            tc[k] = tci+1
            break
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
res = 0
for i in range(n):
    ss = ""
    mod = 0
    for j in range(i, n):
        ss = ss + s[j]
        mod += int(s[j]) % p
        mod %= p
        #print(ss)
        #print("ss", int(ss) % p, mod)
        if int(ss) % p == 0:
            res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
l_ = len(s)
for i in range(l_):
  for j in range(i,l_):
    j+=1
    a = s[i:j]
    if a != []:
      a = int(''.join(a))
      if a%p == 0:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
c = 0
ans = 0
ls = []
def divi(c):
    for i in range(c+1,n+1):
        #print(s[c:i])
        if int(s[c:i]) % p == 0:
            global ans
            ans += 1
            
            
for i in range(n):
    divi(i)
    
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n, p = [int(s) for s in sys.stdin.readline().strip().split()]
s = sys.stdin.readline().strip()

dic = Counter()
ans = 0

for i in range(n):
    num = int(s[i])
    next_dic = Counter()
    next_dic[num % p] = 1
    for key, val in dic.items():
        rem = (key * 10 + num) % p
        next_dic[rem] += val
    if 0 in next_dic:
        ans += next_dic[0]
    dic = next_dic

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,p=map(int,input().split())
s=input()
res=0
for i in range(N):
    val = int(s[i])
    if val%p==0:
        res += 1
    for j in s[i+1:]:
        val = (10*val+int(j))%p
        if val==0:
            res += 1
print(res)

Submission status: Time Limit Exceeded

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

dp=[[0 for _ in range(p)] for _ in range(n+1)]
for i in range(1,n+1):
    dp[i][int(s[i-1])%p]=1
    for j in range(p):
        dp[i][(j*10+int(s[i-1]))%p]+=dp[i-1][j]
print(sum([dp[i][0] for i in range(1,n+1)]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

n,p = map(int, input().split())
s=input()
ct=0
for i in range(n):
  for j in range(i+1,n+1):
    cn=int(s[i:j])
    ct+=(cn%p==0)

print(ct)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

cnt = 0

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
ans = 0
x0 = [0]*p
y = [0]*p
for i in range(p):
  y[i] = (i*10)%p
for t in s:
  x1 = [0]*p
  z = int(t)
  x1[z%p] = 1
  for j in range(p):
    x1[(y[j]+z)%p] += x0[j]
  x0 = x1
  ans += x0[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n, p = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

def main():
    dp = [0] * p
    res = 0
    for d in s:
        d = int(d)
        nex = [0] * p
        for i in range(p):
            nex[(i*10+d)%p] += dp[i]
        nex[d%p] += 1
        dp = nex
        res += dp[0]
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().split()]
S = list(input())
DP = [[0]*P for i in range(N+1)]
amari =[[(a*10+num)%P for a in range(P)]for num in range(10)]#amari[num][a]
tasi = 0
if P not in[2,5]:
    for j,s in enumerate(S):
        Num = int(s)
        tasi += DP[j][0]
        for a in range(P):
            DP[j+1][amari[Num][a]] = DP[j][a]
        DP[j+1][Num%P] += 1
    print(DP[N][0] + tasi)
else:
    for j,s in enumerate(S):
        Num = int(s)
        tasi += DP[j][0]
        for a in range(P):
            DP[j+1][amari[Num][a]] += DP[j][a]
        DP[j+1][Num%P] += 1
    print(DP[N][0] + tasi)

Submission status: Time Limit Exceeded

Solution code:
# abc 158
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, P = map(int, readline().split())
S = list(readline().strip().decode('utf-8'))

answer = 0
for i in range(0, N):
    for j in range(0, N-i):
        begin = i
        end = i + j + 1
        number = int("".join(S[begin:end]))
        if number % P == 0: 
            answer += 1
print(answer)

Submission status: Time Limit Exceeded

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

cur = 0
dp = [0]*N
if S[N-1]%P == 0: dp[N-1] = 1

for a in range(1,N):
    cur = S[N-a-1]
    if cur%P == 0:
        dp[N-a-1] = dp[N-a]+1
    else:
        for b in range(N-a,N):
            cur = cur*10+S[b]
            if cur%P == 0:
                if b != N-1:
                    dp[N-a-1] = dp[b+1]+1
                    break
                else:
                    dp[N-a-1] += 1

print(sum(dp))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, P = map(int,input().split())
N,P=int(N),int(P)
S = str(input())
count=0
for i in range(0,N):
    for j in range(i+1,N+1):
        x=int(S[i:j])
        if x%P==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter

def main():
    N, P = [int(x) for x in input().split()]
    S = input()
    counter = Counter()
    ans = 0
    for x, y in itertools.combinations([x for x in range(N+1)], 2):
        counter[S[x:y]] += 1
    for key, val in counter.items():
        if int(key) % P == 0:
            ans += val
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    count = 0
    for i in range(n):
        for j in range(i, n):
            t = int(s[i: j + 1])
            if t % p == 0:
                count += 1
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a, b = [int(c) for c in input().split(" ")]
S = input()
count = 0
for j in range(a):
  for i in range(1, a - j + 1):
      subStr = S[j:j+i]
      if (int(subStr) % b == 0):
          count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd"""

N,P=map(int,input().split())
S=input()
dp=[[0 for i in range(P)] for n in range(N)]
#visited=set()
for n,s in enumerate(S):
    s=int(s)
    for i in range(P):
        A=(i*10+s)%P
        dp[n][A]+=dp[n-1][i]
    dp[n][s%P]+=1


count=0
for i in dp:
    count+=i[0]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = [int(i) for i in input().split()]
S = input()
DP = [[0]*P for i in range(N+1)]
amari =[[(a*10+num)%P for a in range(P)]for num in range(10)]#amari[num][a]
tasi = 0
for j,s in enumerate(S):
    Num = int(s)
    tasi += DP[j][0]
    for a in range(P):
        DP[j+1][amari[Num][a]] += DP[j][a]
    DP[j+1][Num%P] += 1
print(DP[N][0] + tasi)

Submission status: Time Limit Exceeded

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

mod_10=10%p

#余りがkとなる組み合わせの数の配列

m_l=[0 for i in range(p)]

dp=[0 for i in range(p)]
dp2=[0 for i in range(p)]
st=int(s[0])%p
dp[st]+=1
m_l[st]+=1
use_set={st}

for i in range(1,n):
    tmp_set=set()
    mod_i = int(s[i])%p
    tmp_set.add(mod_i)
    dp2[mod_i]+=1
    for num in use_set:
        tmp_num=(mod_i+mod_10*num)%p
        tmp_set.add(tmp_num)
        dp2[tmp_num]+=dp[num]
        dp[num]=0
    
    dp,dp2 = dp2,dp
    tmp_set, use_set = use_set,tmp_set
    for num in use_set:
        m_l[num]+=dp[num]

print(m_l[0])

Submission status: Time Limit Exceeded

Solution code:
def iin(): return int(input())
def iln(): return list(map(int, input().split()))

# N, P = [4,3]
# S = "3543"
#
# N, P = [4,2]
# S = "2020"
#
# N, P = [20,11]
# S = "33883322005544116655"

N, P = iln()
S = input()

digits = []
for c in S:
    digits.append(int(c))

multipiler_values = [10 ** i for i in range(N)]
def to_int(digits, start, end):
    result = 0
    multiplier_idx = 0
    for j in range(end, start - 1, -1):
        if digits[j] > 0:
            result += multipiler_values[multiplier_idx] * digits[j]
        multiplier_idx += 1
    return result

count = 0
for i in range(N):
    for j in range(i, N):
        # substring [i..j]
        num = to_int(digits, i, j)
        if num % P == 0:
            count += 1


print(count)

Submission status: Time Limit Exceeded

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

def gen(n):
  for l in range(0, n):
    for r in range(l+1, n+1):
      yield slice(l, r)

t = 0
for i in gen(N):
  if int(S[i]) % P == 0:
    t += 1
print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    N, P, S = read().decode('utf-8').split()
    N = int(N)
    P = int(P)
    cnt = 0
    S = '0' + S
    for i in range(1,N+1):
        for j in range(1, N - i + 2):
            num = int(S[j:i+j])
            if num % P == 0:
                cnt += 1
    print(cnt)

    return
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, collections
range = xrange
input = raw_input

n, p = [int(x) for x in input().split()]
A = [ord(x) - 48 for x in input()]


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


DP = [0]*p
ans = 0
POW = 1
ind0 = 0
for a in reversed(A):
    DP[ind0] += 1
    DP = [DP[(a * POW + i) % p] for i in range(p)]
    #ind0 = (a * POW + ind0) % p
    ans += DP[ind0]
    POW = POW * 10 % p
print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

    cnt = 0

    for i in range(N):
        n = SI[i]
        if n % P == 0:
            cnt += 1
        for j in range(i + 1, N):
            n = n * 10 + SI[j]
            if n % P == 0:
                cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
N ,P= map(int,input().split())
S = input()
if P != 2 and P != 5:
    mod_dic ={}
    mod_dic[0] = 1
    for i in range(len(S)):
        num  = int(S[len(S)-i-1:])
        mod = num%P
        if mod not in mod_dic:
            mod_dic[mod] = 1
        else:
            mod_dic[mod] += 1
        ans = 0
    a = list(mod_dic.values())
    for i in range(len(a)):
            ans += a[i] * (a[i]-1) //2
    print(ans)
elif P == 2:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%2 == 0:
            ans += N-i
    print(ans)
else:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%5 == 0:
            ans += N-i
    print(ans)

Submission status: Time Limit Exceeded

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

"""
from collections import deque

s = deque(input())
q = int(input())

for _ in range(q):
  Q = [x for x in input().split()]
  if Q[0] == '1':
    s.reverse()
  else:
    if Q[1] == '1':
      s.appendleft(Q[2])
    else:
      s.append(Q[2])

print('' . join(s))
"""
memo = []
ans = 0
for i in range(len(s)):
  for j in range(len(s)):
    j+=1
    a = s[i:j]
    if a != []:
      a = int(''.join(a))
      if a%p == 0:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs

	
def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	s=np.array([int(c) for c in s])
	s0=s.copy()
	ans=0
	lenS=len(s)
	for i0 in range(lenS):
		r=s%p
		ans+=(r==0).sum()
		if i0<lenS-1:
			s0=s0[1:]
			s10=r[:-1]
			s=s10*10+s0
	print(ans)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

import sys
input = sys.stdin.readline

N, P = map(int, input().split())
S = input().strip()
lenP = len(str(P))

# naive method
count = 0
for i in range(N):
    M = int(S[i:])
    sM = S[i:]

    # 先頭の0の個数
    c0 = 0
    ci = 0
    if len(sM) > 1:
        while sM[ci] == '0':
            c0 += 1
            ci += 1
    if M == 0:
        c0 += 1

    c = 0
    lM = [M]
    while M > 0:
        if M % P == 0:
            c += 1
        M //= 10
        lM.append(M)

    # print(i, M, c, lM, c0)
    count += (c + c0)

print(count)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
S = input()
amarilist = [0 for i in range(P)]
zeroamari = [0 for i in range(P)]
ans = 0
for s in S:
    s = int(s)
    y = s % P
    nextamari = list(zeroamari)
    for i in range(P):
        x = 10 * i % P
        nextamari[x] += amarilist[i]
        #print(nextamari)
    if y == 0:
        amarilist = nextamari
    else:
        amarilist = nextamari[-1*y:]+nextamari[:-1*y]
    #print(amarilist,y)
    amarilist[y] += 1
    ans += amarilist[0]
    #print(amarilist[0],ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
N,P=[int(i) for i in input().split(" ")]
S=input()

if P==2 or P==5:
    retval=0
    for i,s in enumerate(S):
        if(int(s)%P==0):
            retval+=(i+1)
    print(retval)
    sys.exit()


S+='0'
d={}
S=int(S)
for i in range(1,N+2):
    mod=(S%(10**i))%P
    tmp=d.get(mod,0)+1
    d[mod]=tmp

retval=0
for key in d:
    retval+=(d[key]*(d[key]-1)//2)
print(retval)

Submission status: Time Limit Exceeded

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

num = 0
count = 0
for i in range(N):
    x = int(S[i]) % P
    if x == 0:
        count += 1
    for j in range(i + 1, N):
        x = (10 * x + int(S[j])) % P
        if x == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

def keychange(dic,x):
    newdic = {}
    for k in dic:
        b = (k*10 + x) % p
        newdic[b] = dic[k]
    return newdic
dic = {}
count = 0
for i in range(n):
    x = s[i] % p
    dic = keychange(dic,x)
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1
    if 0 in dic:
        count += dic[0]
print(count)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    t1 = s1[i]
    t1p = t1%p
    if t1p == 0:
        ans += 1
    for j in range(i+1, n):
        t2 = t1p*10 + s1[j]
        t1p = t2%p
        if t1p == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

L = [0 for i in range(P)]
nL = [0 for i in range(P)]

ans = 0

for i in range(N):
  s = int(S[i])
  nL[s%P] += 1
  for j in range(P):## ADD s
    nj = (j * 10 + s) % P
    nL[nj] += L[j]
  for j in range(P):
    L[j] = nL[j]
    nL[j] = 0
#L = nL.copy()
  ans += L[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def waru(d):
    return d % p == 0 

ans = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if waru(int(s[i:j+1])):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,P=[int(i) for i in input().split(" ")]
S=input()

if P==2 or P==5:
    retval=0
    for i,s in enumerate(S):
        if(int(s)%P==0):
            retval+=(i+1)
    print(retval)
    sys.exit()


S+='0'
d={}
for i in range(1,len(S)+1):
    mod=(int(S)%(10**i))%P
    tmp=d.get(mod,0)+1
    d[mod]=tmp

retval=0
for key in d:
    retval+=(d[key]*(d[key]-1)//2)
print(retval)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dic = defaultdict(int)
for i in range(len(S)):
    for j in range(i + 1, len(S) + 1):
        # print('i j', i, j, S[i:j])
        key = S[i:j]
        dic[key] += 1
# print(dic)

ans = 0
for key, value in dic.items():
    key = int(key)
    if key % P == 0:
        ans += value
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

# List of ints
def LI(): return list(map(int, sys.stdin.readline().split()))

# Single int
def I(): return int(sys.stdin.readline())

# List, which contains Lists of chars (not strings)
def LS():return list(map(list, sys.stdin.readline().split()))

# Single List of chars (not strings)
def S(): return list(sys.stdin.readline())[:-1]

# List of "n" integers from "n" lines.
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
# List of "n" Lists of integers
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l


# Runtime Complexity: O(?)
# Space Complexity: O(?)
# Solution
N, P = LI()
s = sys.stdin.readline().split()[0]

# print(N, P, S)

res = 0
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        num = int(s[i:j])

        if num % P == 0:
            res += 1

print(res)

Submission status: Time Limit Exceeded

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

def count_num(target_str):
  cnt = 0
  for i in range(len(target_str)):
    target = int(target_str[:i+1])
    if target % p == 0:
      cnt += 1
  return cnt

result = 0
for i in range(n):
  result += count_num(s[i:])
print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a, b = [int(c) for c in input().split(" ")]
S = input()
count = 0
for i in range(1, a):
  for j in range(0, a):
      if (j+i <= a+1):
          subStr = S[j:j+i]
          if (len(subStr) == i):
            if (int(subStr) % b == 0):
                count+=1
if (int(S) % b == 0):
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

lst = [[] for _ in range(10)]

# 0のときは調べなくてよい（無視）
for i in range(1, 10):
	warareru = i
	for n in range(N):
		if n != 0: warareru *= 10
		lst[i].append(warareru % P)
		
ans = 0

for i in reversed(range(N)):
	# スタート地点を設定
	mod = 0
	keta = 0
	for j in range(i, -1, -1):
		keta += 1
		if S[j] != 0:
			mod += lst[S[j]][keta - 1]
			mod %= P
		if mod == 0: ans += 1
			
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * power(10, i, P)
        l[i] = a%P
        b += (ls[i]+ l[i])
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//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 = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
for i in range(n):
    q=0
    for j in range(i,n):
        q=q*10+s[j]
        if q%p==0:
            answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

    def search(i, n):
        if i >= N:
            return 0
        n = n * 10 + int(S[i])
        cnt = 1 if n % P == 0 else 0
        cnt += search(i + 1, n)
        return cnt

    cnt = 0

    for i in range(N):
        cnt += search(i, 0)

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
N,P=[int(i) for i in input().split(" ")]
S=input()

if P==2 or P==5:
    retval=0
    for i,s in enumerate(S):
        if(int(s)%P==0):
            retval+=(i+1)
    print(retval)
    sys.exit()

mods=[]
S+='0'
for i in range(1,len(S)+1):
    mods.append((int(S)%(10**i))%P)

c=Counter(mods)

retval=0
for i in c.items():
    retval+=(i[1]*(i[1]-1)//2)
print(retval)

Submission status: Time Limit Exceeded

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

L = [0 for i in range(P)]
ans = 0

for i in range(N):
  s = int(S[i])
  nL = [0 for i in range(P)]
  nL[s%P] += 1
  for j in range(P):## ADD s
    nj = (j * 10 + s) % P
    nL[nj] += L[j]
  L = nL
#L = nL.copy()
  ans += L[0]
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int, input().split())
s = input()
t = 0
test = s[2:5]
for a1 in range(n+1):
  for b1 in range(n+1):
    if a1 < b1:
      s1 = int(s[a1:b1])
      if s1 % p == 0:
        t = t + 1
print(t)

Submission status: Time Limit Exceeded

Solution code:
aaa = input('').split(' ')

a, b = int(aaa[0]), int(aaa[1])
c = input('')
lc = len(c)
s = 0
for i in range(0, lc):
    for j in range(i+1, lc+1):
        num = int(c[i:j])
        if num % b == 0:
            s += 1
print(s)

Submission status: Time Limit Exceeded

Solution code:


def main():

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


    d = {}


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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

dict = {}
for i in range(n):
    for j in range(i+1, n+1):
        N = int(s[i:j])
        if dict.get(N) is None:
            dict[N] = 1
        else:
            dict[N] += 1

ans = 0
for k, v in dict.items():
    if k%p == 0:
        ans += v
print(ans)

Submission status: Time Limit Exceeded

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