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:
def main():
    n, p = map(int, input().split())
    s = input()

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    # u = [int(s[i:]) for i in range(n)]
    u = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += 10 ** i * int(char)
        u.append(t)
    u = u[::-1]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return

  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10)
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)
 

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return

  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  s = ''.join(s)
  for r in range(n):
    remains[-(r+1)] = int(s[n - r - 1:n]) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return

  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remains[-(r+1)] = int(''.join(s[n - r - 1:n])) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10)
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)
  

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    u = [int(s[i:]) for i in range(n)]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = [0] * p
    for remainder in remainders:
        d[remainder] += 1
    answer = 0
    for count in d:
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Submission status: Time Limit Exceeded

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

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    u = [int(s[i:]) for i in range(n)]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=list(str(input()))
n = N*(N+1)/2
d=0
while len(S)>0:
    for i in range(len(S)):
        if int(''.join(S[0:i+1]))%P == 0:
            d+=1
        if i == len(S)-1:
            S.remove(S[0])

print(d)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,P = map(int,input().split())
  S = list(map(int,list(input())))
  S=S[::-1]
  ans = 0
  if P==2:
    l = [0,2,4,6,8]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i
  elif P==5:
    l=[0,5]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i

  else:
    l = [0]*P
    a=0
    for i in range(N):
      a+=(S[i]*10**i)%P
      a%=P
      l[a]+=1
    ans+=l[0]
    for i in l:
      ans+=i*(i-1)//2

  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
S = list(map(int,list(input())))
S=S[::-1]
ans = 0
from collections import Counter
if P==2:
  l = [0,2,4,6,8]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
elif P==5:
  l=[0,5]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i

else:
  l = [0]*(N+2)
  for i in range(N):
    l[i+1]=l[i]
    l[i+1]+=(S[i]*10**i)%P
    l[i+1]%=P
  l = l[1:N+1:]
  c = Counter(l)
  l = c.items()
  l = sorted(l)
  for k,v in l:
    if k==0:
      ans+=v
    if v==1:
      continue
    else:
      ans+=v*(v-1)//2
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n-1, -1, -1):
    remain = (int(s[r]) * x) % p
    remains[r] = (remains[r+1] + remain) % p
    counts[remains[r]] += 1
    x = (x * 10)
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
mod = [0]*P
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)
else:
    un1 = 0
    un = 0
    for i in range(N-1, -1, -1):
        a = int(S[i])*10**un + un1
        un += 1
        un1 = a
        mod[a%P]+=1
    ans += mod[0]  
    for i in range(P):
        ans += mod[i]*(mod[i]-1)/2
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#
import sys
import math
#import numpy as np
import itertools
from collections import Counter
# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    d=1
    for i in range(n-1,-1,-1):
        q = (d*s[i]+q)%p
        x.append(q)
        d = (d * 10)
    #print(x)
    counter = Counter(x)
    #print(counter)

    for k in counter:
    #    print(k)
        if k==0:
            answer += counter[k] * (counter[k]+1) // 2
        else:
            answer += counter[k] * (counter[k]-1) // 2

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()


ikeru=[U(x)%p for x in range(n)]+[0]
ans=0
C=Counter(ikeru)
for t in C.values():
    if t ==0:continue
    ans+= t*(t-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    # 入力
    N, P = map(int, input().split())
    S = input()
    
    # U[i]：Sのi文字目からN文字目までを整数化した値
    U = [0 for _ in range(N+1)]
    tmp = ""
    for i,s in enumerate(reversed(S)):
        tmp = s + tmp
        U[N-i-1] = int(tmp)
    # print(U)

    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            int_s = int(s)
            if int_s % P == 0:
                ans += i+1
    else:
        mods = {}
        for i in range(P):
            mods[i] = 0
        for ui in reversed(U):
            tmp_mod = ui % P
            ans += mods[tmp_mod]
            mods[tmp_mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*10**(n-i)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  x = 1
  for r in range(n-1, -1, -1):
    remain = (int(s[r]) * x) % p
    remains[r] = (remains[r+1] + remain) % p
    x *= 10
  
  counts = [0] * p
  for remain in remains:
    counts[remain] += 1
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0]
  for r in range(n):
    remains.append(int(s[-(r+1):]) % p)
  remains.reverse()
  
  counts = [0] * p
  for remain in remains:
    counts[remain] += 1
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    m = 0
    for i in range(n):
        m += int(s[-1-i])*(10**(i))
        mp = m % p
        mod[mp] += 1
    for m in mod:
        ans += m*(m+1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from copy import deepcopy

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  for r in range(n-1, -1, -1):
    remain = (int(s[r]) * (10 ** ((n-1)-r))) % p
    remains[r] = (remains[r+1] + remain) % p
  
  remains = [0]
  for r in range(n):
    remains.append(int(s[-(r+1):]) % p)
  remains.reverse()
  
  counts = [0] * p
  for remain in remains:
    counts[remain] += 1
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    lst = [0] * P
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    lst = [0] * P
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    ans = 0
    T = collections.Counter(T).values()
    for v in T:
        ans += v * (v - 1) // 2
    print(ans)

Submission status: Time Limit Exceeded

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[int(s[i:])%p for i in range(n)]+[0]
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = list(input())
left_idx = 0
right_idx = N-1
count_multiples = 0
for right_idx in range(N-1, -1, -1):
  current_sum = 0
  for left_idx in range(right_idx, -1, -1):
    current_sum = (current_sum + int(S[left_idx])*pow(10, right_idx-left_idx, P))%P
    count_multiples += int(current_sum==0)
print(count_multiples)

Submission status: Time Limit Exceeded

Solution code:
N,P = map(int,input().split())
s = list(input())
S = [0]*N

for i in range(N):
    S[i] = int(s[i])

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (10**(i-1))
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

else:
    if P == 2:
        for i in range(N):
            if S[i] %2 == 0:
                count += i+1
    if P == 5:
        for i in range(N):
            if S[i] %5 == 0:
                count += i+1

print(count)

Submission status: Time Limit Exceeded

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

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[int(s[i:])%p for i in range(n)]+[0]
    Mod={i:0 for i in range(p)}
    for i in range(n+1):
        Mod[U[i]]+=1
    for i in range(p):
        cnt+=Mod[i]*(Mod[i]-1)//2

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 0
mod = {0: 0}

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    s = int(s)
    for i in range(1, n+1):
        m = s % (10**i) % p
        mod[m] = mod.get(m, -1)+1
    for m in mod.values():
        ans += m*(m+1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = map(int, input().split())
    S = input().strip()
    
    if p == 2 or p == 5:
        count = 0
        digits = '02468' if p == 2 else '05'
        for i, x in enumerate(S, 1):
            if x in digits:
                count += i
        print(count)
    else:
        counter = [0]*p
        for i in range(n-1, -1, -1):
            counter[int(S[i:]) % p] += 1
        print(counter[0] + sum(i*(i-1)//2 for i in counter))

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, p = map(int, input().split())
S = input().strip()

if p == 2 or p == 5:
    count = 0
    digits = '02468' if p == 2 else '05'
    for i, x in enumerate(S, 1):
        if x in digits:
            count += i
    print(count)
else:
    def comb(n):
        if n >= 2:
            return n*(n-1) // 2
        else:
            return 0
    
    counter = [0]*p
    for i in range(n-1, -1, -1):
        counter[int(S[i:]) % p] += 1
    print(counter[0] + sum(comb(i) for i in counter))

Submission status: Time Limit Exceeded

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

ans=0
for i in range(n):
    if dp[i]!=[-1,-1]:
        ans+=dp[i][0]
        if dp[i][1]!=n:
            if dp[dp[i][1]]!=[-1,-1]:
                dp[dp[i][1]][0]+=dp[i][0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, P = [int(i) for i in input().split()]

S = input()

dp = [-1 for i in range(N)]
def dpf(n):
    if n==N:
        return 0
    if dp[n]>=0:
        return dp[n]
    else:
        for i in range(n+1, N+1):
            num = int(S[n:i])
            ##print(num, n, i)
            if num%P == 0 :
                dp[n] = 1 + dpf(i) 
                return dp[n]
        dp[n]=0
        return dp[n]
    

# ans = [0 for i in range(N)]

# def solve(n):
#     if n==N:
#         return 0
#     else:
#         for i in range(n+1, N+1):
#             num = int(S[n:i])
#             ##print(num, n, i)
#             if num%P == 0 :
#                 ans[n] = 1 + solve(i) 
#                 return ans[n]
#         return 0

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:
    count = [0 for i in range(P)]
    for i in range(N):
        count[int(S[i:])%P]+=1

    count = np.array(count)
    print(count[0] + sum((count * (count-1)) // 2))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, p = map(int, input().split())
S = input().strip()

if p == 2 or p == 5:
    count = 0
    digits = '02468' if p == 2 else '05'
    for i, x in enumerate(S, 1):
        if x in digits:
            count += i
    print(count)
else:
    def comb(n):
        if n >= 2:
            return n*(n-1) // 2
        else:
            return 0
    
    counter = [0]*p
    for i in range(n-1, -1, -1):
        counter[int(S[i:]) % p] += 1
    print(counter[0] + sum(int(comb(i)) for i in counter))

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
s = list(input())
s = [int(i) for i in s]
S = []
ans = 0
for i in range(len(s)+1):
    for j in range(1, len(s)+1-i):
        A = 0
        for k in range(len(s[i:i+j])):
            A += s[i+k]*10**(j-k-1)
            
        if A%P==0:
            ans +=1
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

ans = 0
mod = [0 for i in range(p)]
mod[0] = 1

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

print(ans)

Submission status: Time Limit Exceeded

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

    ans=0
    for i in range(n):
        if dp[i]!=[-1,-1]:
            ans+=dp[i][0]
            if dp[i][1]!=n:
                if dp[dp[i][1]]!=[-1,-1]:
                    dp[dp[i][1]][0]+=dp[i][0]
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input().rstrip()
ans=0
l=[0]*p
 
if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            ans+=i+1
 
else:
    for i in range(n):
        mod=int(s[-(i+1):])%p
        ans+=l[mod]
        l[mod]+=1
        if mod==0:
            ans+=1
 
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
for i in range(n):
    if dp[i]!=[-1,-1]:
        ans+=dp[i][0]
        if dp[i][1]!=n:
            if dp[dp[i][1]]!=[-1,-1]:
                dp[dp[i][1]][0]+=dp[i][0]

print(ans)

Submission status: Time Limit Exceeded

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

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sp = [0]*n
  sp[n-1] = s[n-1]%p
  cnt[sp[n-1]] += 1
  for i in range(1,n):
    sp[n-i-1] = (sp[n-i]+s[n-i-1]*(10**i%p))%p
    cnt[sp[n-i-1]] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    for i in range(len(S)-1, -1, -1):
        s = int(S[i:])
        m = s % P
        if m == 0:
            p[m] += 1
            ans += p[m]
        else:
            ans += p[m]
            p[m] += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    h = defaultdict(int)
    ans = 0
    for i in range(len(S)-1, -1, -1):
        s = int(S[i:])
        m = s % P
        if m == 0:
            h[m] += 1
            ans += h[m]
        else:
            ans += h[m]
            h[m] += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*10**i
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*10**i
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += max(lp[i]*(lp[i]-1)//2, 0)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import time

def main():
    n,p = tuple([int(t)for t in input().split()])
 
    s = input()[::-1]
    s_num = [int(x) for x in s]

    subs = [0]*p
    counter =0

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

    cunum = 0
    for i,sn in enumerate(s_num):
        cunum += sn * 10**i
        subs[cunum%p] +=1

    counter+=subs[0]
 
    for i in range(p):
        counter+= subs[i]*(subs[i]-1)//2
 
    print(counter)
 
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:
        answer = 0
        for i in range(N):
            if int(S[i])%P == 0:
                answer += i+1
        print(answer)

        return
    amari = [0]*N

    for i in range(N-1,-1,-1):
        num = int(S[i:N])
        amari[i]=num%P
    from collections import Counter
    counter = Counter(amari)
    answer = 0
    for _,value in counter.items():
        answer += (value*(value-1))//2
    answer += amari.count(0)
    print(answer)  
    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 = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = (c * w + k) % p
        cnt[k] += 1
        w *= 10

    ans = 0
    for i in range(p):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n,p=list(map(int,input().split()))
s=[int(x) for x in sys.stdin.readline().strip()]
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if s[i]%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]==5 or s[i]==0:
            cnt+=i+1
else:
    x=0
    for i in range(n-1,-1,-1):
        x=s[i]*(10**(n-1-i))+x
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, P = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1
else:
    U = [0] * (N+1)
    count = [0] * P
    count[0] = 1
    factor = 10
    for i in range(N)[::-1]:
        x = S[i] * 10**(N-i-1) + U[i+1]
        U[i] = (S[i] * factor + U[i+1]) % P
        factor = factor * 10 % P
        ans += count[U[i]]
        count[U[i]] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int,input().split())
s = str(input())
mods = [(i*10)%p for i in range(p)]
sums = [0] * p

tmp = 0
dp = [[0]*p for i in range(n+1)]
for i in range(1,n+1):
    now = int(s[i-1])%p
    dp[i][now] += 1
    for j in range(p):
        dp[i][(mods[j]+now)%p] += dp[i-1][j]
#         tmp[(mods[j]+now)%p] += sums[j]
print(sum([dp[i][0] for i in range(n+1)]))
# print(*dp,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    for i in range(n-1,-1,-1):
        x=int(s[i:])
        reslst[x%p]+=1
    reslst[0]+=1

    for i in range(p):
        j=reslst[i]

        cnt+=j*(j-1)//2

print(cnt)