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

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

  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
    chk= [i*(i-1)/2 for i in chk]
    print(int(sum(chk)))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,p = [int(i) for i in 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)
    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
  chk= [i*(i-1)/2 for i in chk]
  print(int(sum(chk)))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
INPUT=input().split()
N=int(INPUT[0])
P=int(INPUT[1])
S=str(input())
"""
constant:N: 文字列Sの長さ
constant:P: 素数 2~10000
constant:S: 0~9からなる文字列
"""
ans=0
"""
variable:ans: Pで割り切れるものの個数
"""
for _ in range(1,N+1):
    """
    variable:_: 部分列の長さ。1~Nまで
    """
    for _a in range(N+1-_):
        """
        variable:_a: 部分列の頭のSにおける位置
        """
        x=int(S[_a:_+_a])
        ans+= 1- (x%P+P-1)//P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
INPUT=input().split()
N=int(INPUT[0])
P=int(INPUT[1])
S=str(input())
"""
constant:N: 文字列Sの長さ
constant:P: 素数 2~10000
constant:S: 0~9からなる文字列
"""
ans=0
"""
variable:ans: Pで割り切れるものの個数
"""
for _ in range(1,N+1):
    """
    variable:_: 部分列の長さ。1~Nまで
    """
    for _a in range(N+1-_):
        """
        variable:_a: 部分列の頭のSにおける位置
        """
        x=int(S[_a:_+_a])
        if (x%P==0): ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

s_part_int = []
for i in range(n+1):
    for j in range(i+1, n+1):
        s_part_int.append(int(s[i:j]))

print([i % p for i in s_part_int].count(0))

Submission status: Time Limit Exceeded

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

dp = [[0]*p for i in range(n)]
for i in range(n): dp[i][0] = 1
dp[0][s[0]%p] += 1

for i in range(n-1):
        for j in range(p):
                dp[i+1][(j*10+s[i+1])%p] += dp[i][j]


ans = -n
for i in dp: ans += i[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=list(map(int,list(input()[::-1])))
if p in [2,5]:
  ans=0
  for i in range(n):
    if s[-i-1]%p==0:ans+=i+1
  print(ans)
  exit()
from collections import defaultdict
d=defaultdict(int)
t=0
d[t]+=1
for i in range(n):
  t+=(10**i)*s[i]
  t%=p
  d[t]+=1
print(sum(d[i]*(d[i]-1)//2 for i in range(p)))

Submission status: Time Limit Exceeded

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

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

U=[0]*(N+1)

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

Submission status: Time Limit Exceeded

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

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

U=[0]*(N+1)

for i in range(N):
  s=S[i:]
  s=int(s)
  U[i]+=s%P

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
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:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*10**i
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.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()

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:
    d=defaultdict(int)
    for i in range(N):
        a=int(S[N-i-1:N])%P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import product

def comb(n):
    if n-1<0:
        return 0
    return n*(n-1)//2


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

ans = 0

if P==2 or P==5:
    for i in range(N):
        # if S//(10**(N-1-i)) % P == 0:
        if int(S[i]) % P == 0:
            ans += i+1
else:
    R=[0]*P
    for i in range(N):
        # r = S%(10**(N-i)) % P
        r = int(S[i::]) % P
        R[r] += 1
    tmp = [comb(i) for i in R]
    ans = sum(tmp)+R[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import product

def comb(n):
    if n-1<0:
        return 0
    return n*(n-1)//2


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

ans = 0

if P==2 or P==5:
    for i in range(N):
        if S//(10**(N-1-i)) % P == 0:
            ans += i+1
else:
    R=[0]*P
    for i in range(N):
        r = S%(10**(N-i)) % P
        R[r] += 1
    tmp = [comb(i) for i in R]
    ans = sum(tmp)+R[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import product

def comb(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n)//math.factorial(n-r)//math.factorial(r)


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

ans = 0

if P==2 or P==5:
    for i in range(N):
        if S//(10**(N-1-i)) % P == 0:
            ans += i+1
else:
    R=[0]*P
    for i in range(N):
        r = S%(10**(N-i)) % P
        R[r] += 1
    tmp = [comb(i, 2) for i in R]
    ans = sum(tmp)+R[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, p = [int(c) for c in input().split()]
s = input()    

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + pow(10, n-i-1) * int(s[i])) % p
#         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Time Limit Exceeded

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

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + pow(10, n-i-1) * int(s[i])) % p
#         tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Time Limit Exceeded

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

if p in (2,5):
    a = tuple(int(c)%p for c in s)
    out = 0
    for i,x in enumerate(a):
        if x==0:
            out += (i + 1)
else:
    a = [0]*n
    tmp = 0
    for i in reversed(range(n)):
        tmp = (tmp + 10**(n-i-1) * int(s[i])) % p
        a[i] = tmp
    d = {i: 0 for i in range(p)}
    d[0] = 1
    out = 0
    for x in a[::-1]:
        out += d[x]
        d[x] += 1
print(out)

Submission status: Time Limit Exceeded

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

ans = 0
tmp = ''

for i in range(n):
    tmp = s[i::]

    for j in range(1,len(tmp)+1):
        if(p in [2,5] and int(tmp[j-1]) == p):
            ans = ans + 1    
        elif((int(tmp[0:j]) % p) == 0):
           ans = ans + 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

if p == 2 or p == 5:
    ans = 0
    mods = map(lambda x: int(x) % p, S)
    for idx, mod in enumerate(mods):
        if mod == 0:
            ans += n - idx
    print(ans)
    exit()

mods = [0]
num = 0
for digit, s in enumerate(S):
    num += int(s) * 10 ** digit
    num %= p
    mods.append(num)

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

if p == 2 or p == 5:
    ans = 0
    mods = map(lambda x: int(x) % p, S)
    for idx, mod in enumerate(mods):
        if mod == 0:
            ans += n - idx
    print(ans)
    exit()

mods = [0]
num = 0
for digit, s in enumerate(S):
    num += int(s) * 10 ** digit
    mod = num % p
    mods.append(mod)

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-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):
    s=int(S[i:j])
    if s%P==0:
      ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

count = 0

i = 1
while i <= n:
    j = 0
    while j + i <= n:
        if int(s[j:j+i]) %p == 0:
            count += 1
        j += 1
    i += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def sol(s, p):
	n = len(s)
	cnt = 0
	if p == 2 or p == 5:
		for i in range(n):
			if (s[i] % p == 0):
				cnt += i + 1
	else:
		pre = [0] * (n+2)
		pre[n+1] = 0
		b = 1
		for i in range(n, 0, -1):
			pre[i] = (pre[i+1] + s[i-1] * b) % p
			b *= 10
		rec = [0] * p
		rec[0] = 1
		for i in range(n, 0, -1):
			cnt += rec[pre[i]]
			rec[pre[i]] += 1
	return cnt

if __name__ == "__main__":
	n, p = map(int, input().split())
	s = input()
	print (sol([int(i) for i in s], p))

Submission status: Time Limit Exceeded

Solution code:
def f(p, s):
  n = len(s)
  count = 0
  for i in range(n):
    for j in range(i, n):
      count += int(s[i:j+1]) % p == 0
  print(count)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,p=map(int,input().split())
    s=list(map(int,list(input())))
    dp=[[0]*p for _ in range(n+1)]
    for i in range(1,n+1):
      dp[i][s[i-1]%p]+=1
      for j in range(0,p):
        dp[i][(j*10+s[i-1])%p]+=dp[i-1][j]
    ans=0
    for i in range(1,n+1):
      ans+=dp[i][0]
    print(ans)     

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
    #     print(tmp)
    #     ans += dp[tmp]
    #     dp[tmp] += 1
    # print(dp)

    # ベースの考え方。https://drken1215.hatenablog.com/entry/2020/03/08/020200
    # 素数pで割ったあまりは、0, 1, 2, ... p - 1になる。
    # 例えば、s=152467, p=3とする
    # 0 mod 3 = 0 (単独でも1つになるので、便宜上加える)
    # 7 mod 3 = 1
    # 67 mod 3 = 1
    # 467 mod 3 = 2
    # 2467 mod 3 = 1
    # 52467 mod 3 = 0
    # 152467 mod 3 = 1
    # となる。
    # 例えば、x mod 3 = 1について、考える。これは、7, 67, 2467, 152467の4つある。
    # これから、67 - 7 = 60で、3で割り切れる。2467 - 7 = 2560で、3で割り切れる。
    # このように、4つのうち2つを組み合わせれば、あまりの数が同じなので、p(3)で割り切れる組み合わせ
    # を作ることができる。
    # 467 mod 3 = 2については、あまりが2はコレしかないので、組み合わせることはできず、0となる。
    # また、あまりが2のものと、あまりが1のもの2個で組み合わせることはできない。なぜなら、
    # 467-67-7で組み合わせたところで、67と7が互いに相殺してしまうし、結果も393という、sの中に存在しない文字になるからである。
    # 基本はこれであり、下記のようになるが、これでは遅い。
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i:])) % p
    #     dp[tmp] += 1
    # for i in dp:
    #     ans += nCr(i, 2)
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i:])) % p
        ans += dp[tmp]
        dp[tmp] += 1
print(ans)

'''
6 3
152467
'''

Submission status: Time Limit Exceeded

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

mod = (10 ** 9 + 7) ** 5 # (modの値をすごく大きくすれば（5乗とか）、普通のnCrとして使える)
MAX = 10 ** 5 + 1 # これは変動するので注意

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
    #     print(tmp)
    #     ans += dp[tmp]
    #     dp[tmp] += 1
    # print(dp)

    # ベースの考え方。https://drken1215.hatenablog.com/entry/2020/03/08/020200
    # 素数pで割ったあまりは、0, 1, 2, ... p - 1になる。
    # 例えば、s=152467, p=3とする
    # 0 mod 3 = 0 (単独でも1つになるので、便宜上加える)
    # 7 mod 3 = 1
    # 67 mod 3 = 1
    # 467 mod 3 = 2
    # 2467 mod 3 = 1
    # 52467 mod 3 = 0
    # 152467 mod 3 = 1
    # となる。
    # 例えば、x mod 3 = 1について、考える。これは、7, 67, 2467, 152467の4つある。
    # これから、67 - 7 = 60で、3で割り切れる。2467 - 7 = 2560で、3で割り切れる。
    # このように、4つのうち2つを組み合わせれば、あまりの数が同じなので、p(3)で割り切れる組み合わせ
    # を作ることができる。
    # 467 mod 3 = 2については、あまりが2はコレしかないので、組み合わせることはできず、0となる。
    # また、あまりが2のものと、あまりが1のもの2個で組み合わせることはできない。なぜなら、
    # 467-67-7で組み合わせたところで、67と7が互いに相殺してしまうし、結果も393という、sの中に存在しない文字になるからである。
    # 基本はこれであり、下記のようになるが、これでは遅い。
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i:])) % p
        dp[tmp] += 1
    # print(dp)
    for i in dp:
        ans += nCr(i, 2)

print(ans)

Submission status: Time Limit Exceeded

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

def nCr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    # dp = [0] * p
    # dp[0] = 1
    # tmp = 0
    # for i in range(n)[::-1]:
    #     tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
    #     ans += dp[tmp]
    #     dp[tmp] += 1
    # print(dp)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# n=桁数、 p=素数
n,p = map(int,input().split())
s = input()

count = 0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

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

for i in range(1,N+1):
    for j in range(N-i+1):
        T.append(int(''.join(S[j:j+i])))

L = np.array(T)
L = L%P
ans = 0
for i in range(len(L)):
    if L[i] == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i]) * 10 ** (n - i - 1) + tmp) % p
        # print(tmp, int(s[i]) * 10 ** (n - i - 1))
        ans += dp[tmp]
        dp[tmp] += 1 
    # print(dp)

print(ans)

Submission status: Time Limit Exceeded

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

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

modP = [0 for _ in range(P)]
modP[0] = 1
for i in range(N) :
    modP[int(S[i:])%P] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            count += (right + 1)
else:
    mod_p_count = [0 for i in range(p)]
    mod_p_count[0] = 1
    for pow in range(1, n + 1):
        sub_s = int(s) % 10**pow
        mod_p_count[sub_s % p] += 1
    for i in mod_p_count:
        count += i*(i - 1) // 2
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            count += (right + 1)
else:
    mod_p_count = [0 for i in range(p)]
    mod_p_count[0] += 1
    for i in range(n):
        sub_s = int(s[i:])
        mod_p_count[sub_s % p] += 1
    for i in mod_p_count:
        count += i*(i - 1) // 2
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            count += (right + 1)
else:
    mod_p_count = {0: 1}
    for i in range(n):
        sub_s = int(s[i:])
        try:
            mod_p_count[sub_s % p] += 1
        except KeyError:
            mod_p_count[sub_s % p] = 1
    for v in mod_p_count.values():
        count += v*(v - 1) // 2
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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


def is_prime(p, s):
    tmp = 0
    sum = 0
    for i in s:
        tmp = (tmp * 10 + i) % p
        if tmp == 0:
            sum += 1
    return sum


n = len(s)
cnt = 0

for i in range(n):
    cnt += is_prime(p, s[i:])

print(cnt)

Submission status: Time Limit Exceeded

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

print(count)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    res = 0

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

else:
    res = 0
    count = [0] * P

    for i in range(N-1, -1, -1):
        n = int(S[i:N])
        r = n % P
        if r == 0: res += 1
        res += count[r]
        count[r] += 1
    
    print(res)

Submission status: Time Limit Exceeded

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

from functools import lru_cache


def main():
    n, p = map(int, input().split())
    s = input().strip()
    mod_dict.clear()

    ans = 0
    for i in range(n):
        for j in range(i, n):
            if is_mod_zero(s, i, j, p):
                ans += 1
    print(ans)


mod_dict = {}


def is_mod_zero(s, i, j, p):
    c = int(s[i:j + 1])
    if c in mod_dict:
        return mod_mem(c, p) == 0
    if c == 0:
        return True
    if c < p:
        return False
    if i == j:
        return mod_mem(int(s[i]), p) == 0
    if c < 100:
        return mod_mem(c, p) == 0

    prev_c = int(s[i:j])
    new_c = int(s[j])
    tp = mod_mem(10, p)

    prev_c_mod = mod_mem(prev_c, p)
    new_c_mod = mod_mem(new_c, p)

    c_mod = ((tp * prev_c_mod) % p + new_c_mod) % p
    mod_dict[c] = c_mod
    return c_mod == 0


def mod_mem(a, p):
    if a in mod_dict:
        return mod_dict[a]

    a_mod = a % p
    mod_dict[a] = a_mod
    return a_mod


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from functools import lru_cache


def main():
    n, p = map(int, input().split())
    s = input().strip()
    mod_dict.clear()

    ans = 0
    for i in range(n):
        for j in range(i, n):
            if is_mod_zero(s, i, j, p):
                ans += 1
    print(ans)


mod_dict = {}


def is_mod_zero(s, i, j, p):
    c = int(s[i:j + 1])
    if c == 0:
        return True
    if c < p:
        return False
    if i == j:
        return mod_mem(int(s[i]), p) == 0
    if c < 100:
        return mod_mem(c, p) == 0

    prev_c = int(s[i:j])
    new_c = int(s[j])
    tp = mod_mem(10, p)

    prev_c_mod = mod_mem(prev_c, p)
    new_c_mod = mod_mem(new_c, p)

    c_mod = ((tp * prev_c_mod) % p + new_c_mod) % p
    mod_dict[c] = c_mod
    return c_mod == 0


def mod_mem(a, p):
    if a in mod_dict:
        return mod_dict[a]

    a_mod = a % p
    mod_dict[a] = a_mod
    return a_mod


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def is_prime(p, s):
    if(s % p == 0):
        return 1
    else:
        return 0


def str_num(s):
    return int(''.join(s))


tmp = deque()

n = len(s)
cnt = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        cnt += is_prime(p, str_num(s[i:j]))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
count=0
s=list(input())
for i in range(n):
  for j in range(n-i):
    m=int(''.join(s[j:j+i+1]))
    if m%p==0:
      count+=1
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):
        s2 = s[j: j + i + 1]
        a = int(''.join(s2))
        if a % p == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if P == 2 or P==5:
    # 左端が2,5となる文字列を見つけてくる
    ans=0
    for i,s in enumerate(S):
        if s%P==0:
            ans+=i+1
    print(ans)
else:
    # mod P の和を足していく
    ans = 0
    from collections import deque
    U=deque()
    U_sum=deque()
    ten = 1
    for i,s in enumerate(S[::-1]):
        new = (s*ten) % P
        U.appendleft(s*10**i % P)
        ten *= 10
        ten %= P
    same_p = [0 for _ in range(P)]
    for i in range(len(U)):
        u = U[-i-1]
        if i == 0:
            U_sum.appendleft(u)
            same_p[u]+=1
            continue
        new = (U_sum[-i]+u) % P
        U_sum.appendleft(new)
        same_p[new] += 1

    for i,p in enumerate(same_p):
        if i == 0:
            # 自分だけでも選択できるから
            ans += p
        ans += int(p*(p-1) / 2)
    print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, P=map(int,input().split())
S = input()
def ma25():
  ret = 0
  for i in range(N):
    if int(S[i])%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  dp[0] = 1
  for i in range(N-1,-1,-1):
    dp[int(S[i:])%P] += 1
  ret = 0
  for m in dp:
    ret += m*(m-1)//2
  print(ret)

if P == 2 or P == 5:
  ma25()
else:
  ma()

Submission status: Time Limit Exceeded

Solution code:
a=input()
b=input()
d='3542'
(n,m)=a.split()
n=int(n)
m=int(m)
k=0
l=[]
for i in range(len(b)):
    for j in range(n-i+1):
        c=b[i:i+j]
        if c!="" and int(c)%m==0:
            k+=1
print(k)

Submission status: Time Limit Exceeded

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

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

x = [0] * p
x[0] = 1
for i in range(n-1, -1, -1):
    x[int(''.join(s[i:])) % p] += 1

ans = 0

for z in x:
    ans += z * (z-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P=map(int,input().split())
S = list(map(int,list(input())))
def ma25():
  ret = 0
  for i in range(N):
    if S[i]%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  ret = 0
  for i in range(N):
    dp_ = [0]*P
    b = S[i]%P
    for j in range(P):
      dp_[(j*10+b)%P] += dp[j]
    dp_[b] += 1
    ret += dp_[0]
    dp = dp_[:]
  print(ret)    
if P == 2 or P == 5:
  ma25()
else:
  ma()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input().lstrip('0')
res = 0
while s != '':
    ss = s
    while ss != '':
        if int(ss) % p == 0:
            res += 1
        ss = ss[0:-1]
    s = s[1:]
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int, input().split())
s = input()
ans = 0
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if 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()

ans = 0
count = int(N * (N + 1) / 2)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P=map(int,input().split())
S = list(map(int,list(input())))
def ma():
  dp = [0]*P
  ret = 0
  for i in range(N):
    dp_ = [0]*P
    b = S[i]%P
    for j in range(P):
      dp_[(j*10+b)%P] += dp[j]
    dp_[b] += 1
    ret += dp_[0]
    dp = dp_[:]
  print(ret)    
ma()

Submission status: Time Limit Exceeded

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


for x in range(len(S)):
    x += 1
    for y in range(len(S)+1-x):
        NUM = int(S[y:y+x])
        if NUM % P == 0:
            count += 1


print(count)

Submission status: Time Limit Exceeded

Solution code:
N, P=map(int,input().split())
S = list(map(int,list(input())))
dp = [0]*P
ret = 0
for i in range(N):
  dp_ = [0]*P
  b = S[i]%P
  for j in range(P):
    dp_[(j*10+b)%P] += dp[j]
  dp_[b] += 1
  ret += dp_[0]
  dp = dp_[:]
print(ret)