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 heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

    if P == 2 or P == 5:
        for i in range(N):
            if s[i] % P == 0:
                ans += N - i
        print(ans)
        return

    cur = 1
    for i in range(N):
        d = s[i] * cur
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        cnts[D[i]] += 1
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1
        cur *= 10

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

    if P == 2 or P == 5:
        for i in range(N):
            if s[i] % P == 0:
                ans += N - i
        print(ans)
        return

    cur = 1
    for i in range(N):
        d = s[i] * cur
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1
        cur *= 10

    for d in D:
        cnts[d] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

    if P == 2 or P == 5:
        for i in range(N):
            if s[i] % P == 0:
                ans += N - i
        print(ans)
        return

    for i in range(N):
        d = s[i] * pow(10, i)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1

    for d in D:
        cnts[d] += 1

    for i in cnts:
        ans += i * (i - 1) // 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):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = [0]*P
    mod_cnt[0] = 1
    for i in range(N):
        mod = int(S[i:]) % P
        mod_cnt[mod] += 1
    ans = 0
    for cnt in mod_cnt:
        ans += (cnt * (cnt-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(N):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = {0: 1}
    for i in range(N):
        mod = int(S[i:]) % P
        if mod in mod_cnt:
            mod_cnt[mod] += 1
        else:
            mod_cnt[mod] = 1
    ans = 0
    for cnt in mod_cnt.values():
        ans += (cnt * (cnt-1)) // 2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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


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


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

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        val[0] += 1
        for i in range(N):
            cur = int(S[N - i - 1 :]) % P
            val[cur] += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


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

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
from collections import defaultdict


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

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    U = [int(S[i:]) % P for i in range(N)]+[0]
    table = Counter()
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, P: int, S: str):
    S = list(map(int, list(S)))
    DP = [defaultdict(int) for _ in range(N)]
    for i in range(N):
        c = S[i]
        for key in DP[i-1]:
            DP[i][(key*10+c) % P] += DP[i-1][key]
        DP[i][c % P] += 1
    print(sum([DP[i][0] for i in range(N)]))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7


def solve(N: int, P: int, S: str):
    DP = [defaultdict(int) for _ in range(N)]
    for i in range(N):
        for key in DP[i-1]:
            DP[i][(key*10+int(S[i])) % P] += DP[i-1][key]
        DP[i][(int(S[i])) % P] += 1
    # print(*DP, sep="\n")
    print(sum([DP[i][0] for i in range(N)]))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)

Submission status: Time Limit Exceeded

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

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

else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        p=int(p)
        total+=p*inv
        S[total%k]+=1
    for i in S:
        ans+=i*(i-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split(sep=" "))
S = input()
count=0
for i in range(0,N,1):
    for j in range(i,N,1):
        tmp = int(S[i:j+1])
        if tmp%P == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    a = [0] + [int(s[-i:]) % p for i in range(1, n+1)]
    for a_i in a:
        cnt[a_i] += 1

    for v in cnt.values():
        ans += v * (v - 1)//2
    print(ans)

Submission status: Time Limit Exceeded

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    # 右端が偶
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    cnt[0] += 1
    a_i = ""
    for i in range(1, n+1):
        a_i = s[-i] + a_i
        cnt[int(a_i) % p] += 1

    for v in cnt.values():
        ans += v * (v - 1)//2
    print(ans)

Submission status: Time Limit Exceeded

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

cnt = defaultdict(int)
ans = 0
if p == 2:
    for i, v in enumerate(s):
        if int(v) % 2 == 0:
            ans += 1 + i
    print(ans)
elif p == 5:
    for i, v in enumerate(s):
        if v == "0" or v == "5":
            ans += 1 + i
    print(ans)
else:
    for i in range(n+1):
        a_i = int(s[-i:]) if i > 0 else 0
        cnt[a_i % p] += 1

    for v in cnt.values():
        ans += v * (v - 1)//2
    print(ans)

Submission status: Time Limit Exceeded

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


ans=0
if P!=2 and P!=5:
  ls=[int(num[i:])%P for i in range(N)]
  count=[0 for _ in range(P)]
  for i in range(N):
    count[ls[i]]+=1
  for i in range(N):
    a=ls[i]
    if a==0:
      ans+=1
    count[a]-=1
    ans+=count[a]
else :
  for i in range(N):
    if int(num[i])%P==0:
      ans+=i+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=[int(s) for s in input().split()]
DP=[[0 for _ in range(i+1)] for i in range(N)]
ls=[int(s)%P for s in list(input())]

count=[[0 for _ in range(P)] for _ in range(N)]


for j in range(N):
  count[j][ls[j]]+=1

for i in range(1,N):
  a=ls[i]
  for k in range(P):
    if count[i-1][k]!=0:
      count[i][(10*k+a)%P]+=count[i-1][k]
  
ans=0
for j in range(N):
  ans+=count[j][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=[int(s) for s in input().split()]
DP=[[0 for _ in range(i+1)] for i in range(N)]
ls=[int(s)%P for s in list(input())]

count=[[0 for _ in range(P)] for _ in range(N)]


for j in range(N):
  count[j][ls[j]]+=1

for i in range(1,N):
  a=ls[i]
  for k in range(P):
    count[i][(10*k+a)%P]+=count[i-1][k]
  
ans=0
for j in range(N):
  ans+=count[j][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=[int(s) for s in input().split()]
DP=[[0 for _ in range(N-i)] for i in range(N)]
ls=[int(s)%P for s in list(input())]

count=0

for j in range(N):
  DP[0][j]=ls[j]
  if DP[0][j]==0:
    count+=1


for i in range(1,N):
  for j in range(N-i):
    DP[i][j]=(DP[i-1][j]*10+DP[0][i+j])%P
    if DP[i][j]==0:
      count+=1
    
print(count)

Submission status: Time Limit Exceeded

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

def main():
    N,P = map(int,input().split())
    S = input()
    
    if 10%P == 0:
        ans = 0
        for i,st in enumerate(S[::-1]):
            num = int(st)
            if num % P == 0:
                ans += N-i
    else:
        ans,base = 0,1
        MOD = 0
        d = defaultdict(int)
        d[0] = 1
        for st in S[::-1]:
            num = int(st)
            MOD = (MOD+num*base)%P
            d[MOD] += 1
            base *= 10
        for v in d.values():
            ans += (v*(v-1))//2
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

m = [0] * N
for i in range(N):
    m[i] = int(S[i:]) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)/2

sum += mc[0]

print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

for n, v in mc.items():
    if v > 1:
        sum += v*(v-1)/2

sum += mc[0]

print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, P = list(map(int,_in[0].split(' ')))  # type:list(int)
    S =     _in[1]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cand_arr = []
    for i in range(N):
        for j in range(N-i):
            cand_arr.append(int(S[j:j+i+1]))
    cnt = 0
    for cand in cand_arr:
        if cand % P == 0:
            cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,P = list(map(int, input().split()))
S = '0'+input()

dp = [[0 for _ in range(P)] for i in range(N+1)]
mod_tab = [[0 for _ in range(10)] for i in range(P)]

for p in range(P):
    for a in range(10):
        mod_tab[p][a] = (p*10+a)%P

dp[1][int(S[1])%P]=1
for i in range(2,N+1):
    dp[i][int(S[i])%P] += 1
    for p in range(P):
        target = mod_tab[p][int(S[i])]
        dp[i][target] += dp[i-1][p]
sum=0
for i in range(1,N+1):
    sum+=dp[i][0]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    ss = map(int, s)
    if 10%p == 0:
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    tens = 10**(n-1)
    for i, si in enumerate(ss):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= si*tens
        tens //= 10
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    ss = map(int, s)
    if 10%p == 0:
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    tens = 10**(n-1)
    for i, si in enumerate(ss):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= si*tens
        tens //= 10
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    keta = n-1
    for i, si in enumerate(s):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= int(si)*10**keta
        keta -= 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    for i in range(n):
        v = int(s[i:])%p
        mu[i] = v
        c[v] += 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*10000
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    for i in range(n):
        v = int(s[i:])%p
        mu[i] = v
        c[v] += 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    u = [int(s[i:]) for i in range(n)]
    mu = [None]*n
    ans = 0
    c = [0]*10000
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    for i, v in enumerate(u):
        m = v%p
        mu[i] = m
        c[m] += 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

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

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

else:
    mm = {}
    for i in range(n - 1, -1, -1):
        u = int(s[i:])
        r = u % p
        if r in mm:
            c += mm[r]
            mm[r] += 1
        else:
            mm[r] = 1

        if r == 0:
            c += 1
        
print(c)

Submission status: Time Limit Exceeded

Solution code:
# from collections import Counter
n, p = map(int, input().split())
s = input()
s += '0'
p_cnt = 0

div_dic = dict(zip(range(p), [0] * p))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            p_cnt += i+1
else:
    for i in range(n+1):
        div_dic[int(s[i:]) % p] += 1

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

Submission status: Time Limit Exceeded

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

div_dic = dict(zip(range(p), [0] * p))

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            p_cnt += i+1
else:
    for i in range(n+1):
        div_dic[int(s[i:]) % p] += 1

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



print(int(p_cnt))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n, p = map(int, input().split())
s = input()
s += '0'
p_cnt = 0
div_list = []

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            p_cnt += i+1
else:
    for i in range(n+1):
        num = int(s[i:])
        div_list.append(num % p)

    div_ol = Counter(div_list)
    for v in div_ol.values():
        p_cnt += v * (v - 1) / 2



print(int(p_cnt))

Submission status: Time Limit Exceeded

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

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

print(p_cnt)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
# Python3 program to Split string into characters 
def split(word): 
    return [char for char in word]  
Numberstring=input()
Numberlist=split(Numberstring)
ans=0
for i in range(0,N):
  currentmodulo=int(Numberlist[i])%P
  if currentmodulo==0:
    ans=ans+1
  for j in range(i+1,N):
    currentmodulo=(currentmodulo*10+int(Numberlist[j]))%P
    if currentmodulo==0:
      ans=ans+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    sys.exit()
    
res = [0] * p
arr = [int(s[i:])%p for i in range(n)]
for i in arr:
    res[i] += 1
for i in res:
    ans += i*(i-1)
ans //= 2
ans += res[0]
    
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7

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

if P == 2:
    ans = 0
    for i, c in enumerate(S):
        if int(c) % 2 == 0:
            ans += i + 1
    print(ans)
elif P == 5:
    ans = 0
    for i, c in enumerate(S):
        if c in ['5', '0']:
            ans += i + 1
    print(ans)
else:
    d = defaultdict(int)
    s = ''
    tenmod = 1
    lastmod = 0
    for i, c in enumerate(reversed(S)):
        s += c
        if i > 0:
            tenmod = tenmod * 10 % P
        lastmod = (int(c) * tenmod % P + lastmod) % P
        d[lastmod] += 1
    ans = 0
    for m, cnt in d.items():
        if m == 0:
            ans += cnt
        ans += cnt * (cnt - 1) // 2
    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):
        p = int(S[i:j])
        ans += 1 if p%P == 0 else 0
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

count = 0
tmp = ''
for i in range(n-1):
  tmp = ''
  #if s[i] == '0':
  #  continue
  
  for j in range(i,n):
    tmp = tmp + s[j]
    if int(tmp) % p ==  0:
      count += 1

if int(s[n-1]) % p == 0:
  count += 1

      
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
n, p = stdin.readline().rstrip().split()
n, p = int(n), int(p)
s = stdin.readline().rstrip()
c = 0
for i in range(n+1):
    for j in range(0,i):
        x = int(s[j:i])
        if x % p == 0:
            c += 1
    
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  
  import math
  def nCr(n, r):
    if n < r:
      return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

  else:
    chk = [0]*p
    chk[0] = 1
    m = 0
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i)+m)%p
      chk[m] += 1
    for i in chk:
      ans += nCr(i,2)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n,p = [int(i) for i in input().split()]
  s = input()
  ans = 0
  import collections

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

  else:
    chk = []
    m = 0
    chk = collections.deque(chk)
    for i in range(n)[::-1]:
      m = (int(s[i])*pow(10,n-1-i)+m)%p
      chk.append(m)
    chk.append(0)
    chk = list(chk)
    c = collections.Counter(chk)
    for i in range(p):
      ans += c[i]*(c[i]-1)/2
    print(int(ans))
if __name__ == '__main__':
    main()