Problem:


Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

1 \leq N \leq 2 \times 10^5

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
digit_dic = {}
dic = {}
for i in range(n, 0, -1):
  tmp = 0
  for j in range(i-1, -1, -1):
    #print(s[j:i])
    #print(j,i)
    digit = i - j - 1
    num = 10 ** digit
    if num not in digit_dic:
      q = num % p
      digit_dic[num] = q
    else:
      q = digit_dic[num]
    num = int(s[j])
    if num not in dic:
      r = num % p
      dic[num] = r
    else:
      r = dic[num]
    q *= r
    q += tmp
    #print(q)
    q %= p
    if q == 0:
      count += 1
    tmp = q
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
digit_dic = {}
for i in range(n, 0, -1):
  tmp = 0
  for j in range(i-1, -1, -1):
    #print(s[j:i])
    #print(j,i)
    digit = i - j - 1
    num = 10 ** digit
    if num not in digit_dic:
      q = num % p
      digit_dic[num] = q
    else:
      q = digit_dic[num]
    q *= int(s[j])
    q += tmp
    #print(q)
    q %= p
    if q == 0:
      count += 1
    tmp = q
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = [int(i) for i in input().split()]
s = input()
ans = 0
pp = 0

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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
total = 0
if P == 2:
  for idx, right_value in enumerate(S, 1):
    if int(int(right_value)%2==0):
      total += idx
elif P == 5:
  valid_options = (0, 5)
  for idx, right_value in enumerate(S, 1):
    if int(int(right_value) in valid_options):
      total += idx
else:
  histo_modsuffix = [0]*P
  for i in range(1, N+1):
    histo_modsuffix[int(S[-i:])%P] += 1
  total = 0
  for val in histo_modsuffix:
    total += val*(val-1)//2
  total += histo_modsuffix[0] # when right hand side is at far end
print(total)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

ans = 0

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

else:
    d = {0: 1}
    for i in range(n):
        if int(s[n-1-i:]) % p not in d:
            d[int(s[n-1-i:]) % p] = 1
        else:
            d[int(s[n - 1 - i:]) % p] += 1

    for dd in d.values():
        ans += dd*(dd-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

ans = 0

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

else:
    b = [int(s[n-1-i:]) % p for i in range(n)] + [0]
    d = Counter(b)

    for dd in d.values():
        ans += dd*(dd-1)//2

print(ans)

Submission status: Time Limit Exceeded

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

amari=[0]*P
amari[0]=1

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

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

for i in range(1,N+1):
  #amari[int(S[-i:])%P]+=1
  amari[sn%(10**i)%P]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
タグ：区間
"""

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

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p *= 10

    cnt = [0]*P
    for i in range(N+1):
        cnt[T[i]%P] += 1

    res = 0
    for c in cnt:
        res += c*(c-1)//2
    print(res)

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:
    M=[0]*p
    M[0]=1
    tmp=0
    for i in range(n):
        tmp+=(int(s[-i-1])*10**i)
        tmp%=p
        ans+=M[tmp%p]
        M[tmp%p]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,p = map(int,input().split())
s=list(input().rstrip())
ans = 0
for i in range(n):
    for j in range(i+1,n+1):
        val = "".join(s[i:j])
        val = int(val)
        if val%p==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, p = [int(i) for i in input().split()]
    s = input()
    ndiv = 0

    d = [int(i) for i in s]

    mods = [i % p for i in range(10)]
    tenmods = [i * 10 % p for i in range(p)]

    for i in range(n):
        sm = d[i] % p
        if sm == 0:
            ndiv += 1
        for j in range(i+1, n):
            sm = (tenmods[sm] + mods[d[j]])
            if sm >= p:
                sm -= p
            if sm == 0:
                ndiv += 1

    print(ndiv)

main()

Submission status: Time Limit Exceeded

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

    ndiv = 0

    d = [int(i) for i in s]

    for i in range(n):
        sm = d[i] % p
        if sm == 0:
            ndiv += 1
        for j in range(i+1, n):
            sm = (sm * 10 + d[j]) % p
            if sm == 0:
                ndiv += 1

    print(ndiv)
    
main()

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):
    if int(S[i:j]) % P == 0:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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()
    
total=[0]*p#pで割った余りで分類
total[0]=1#t[0]=0の分をあらかじめカウント
t=[0]*(n+1)#s[i:n]を格納する用の配列
for i in range(n-1,-1,-1):
    t[i]=t[i+1]+int(s[i])*10**(n-1-i)%p#s[i:n]を漸化式で付け加えていく
    total[t[i]%p]+=1
    
for i in range(p):
    ans+=total[i]*(total[i]-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(n+1):
        if i >= j :
            continue
        else:
            if (j-i) == 1:
                a = int(s[i:j])%p
            else:
                a = (a*10 + int(s[j-1]))%p
            if a == 0:
                cnt += 1

print(cnt)

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(n+1):
        if i >= j :
            continue
        else:
            if int(s[i:j])%p == 0:
                cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
N, P = map(int, input().split())
S = input()
s_mod = [0]*(N+1)

ans = 0
if P == 2:
    for i in range(N):
        ans += ((int(S[-(i+1)])%2) ^ 1) * (N-i)
    print(ans)
    sys.exit()
elif P == 5:
    for i in range(N):
        ans += ((int(S[-(i + 1)]) % 5)==0) * (N - i)
    print(ans)
    sys.exit()


for i in range(N):
    s_mod[i+1] = (10**i*int(S[-(i+1)])+s_mod[i]) % P
c = collections.Counter(s_mod)
for v in c.values():
    ans = (ans + v*(v-1)//2)
print(ans)

Submission status: Time Limit Exceeded

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

end_num = []
end_idx = []

last_P = P%10
for i in range(10):
    num = last_P * i % 10
    if num not in end_num:
        end_num.append(num)
for i, j in enumerate(S):
    if int(j) in end_num:
        end_idx.append(i+1)

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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
def get_pn(n):
    pn = list(range(2, n+1))
    for i in pn:
        pn = [x for x in pn if (x == i or x % i != 0)]
    return pn

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

Submission status: Time Limit Exceeded

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

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

print(res)

Submission status: Time Limit Exceeded

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

mods = [0] * (N+1)
for i in range(N):
  mods[i] = int(S[i:]) % P
c = dict()
for m in mods:
  c[m] = c.get(m, 0)+1

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c[mods[i]]

print(ans)

Submission status: Time Limit Exceeded

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

mods = [0] * (N+1)
for i in range(N):
  mods[i] = int(S[i:]) % P
c = collections.Counter(mods)
c = dict(c)

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c.get(mods[i], 0)

print(ans)

Submission status: Time Limit Exceeded

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

mods = [0] * (N+1)
for i in range(N):
  mods[i] = int(S[i:]) % P
ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c = dict(collections.Counter(mods[i+1:]))
    ans += c.get(mods[i], 0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys 
import collections
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,P = map(int,readline().split())
S = list(map(int,readline().rstrip().decode()))

def solve_2(S):
    cnt = sum(i for i,x in enumerate(S,1) if x % 2 == 0)
    return cnt
def solve_5(S):
    cnt = sum(i for i,x in enumerate(S,1) if x % 5 == 0)
    return cnt
def solve(S):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    mod_cnt = [0]*(len(S))
    S = S[::-1]
    for i in range(len(S)):
        mod_cnt[i] = (mod_cnt[i-1] + S[i] * 10**i) % P
    c = collections.Counter(mod_cnt)
    ans = 0
    ans += mod_cnt.count(0)
    ans += sum( n*(n-1)//2 for n in c.values())
    return ans

print(solve(S))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    N, P = map(int, input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mod = [0] * P
        mod[0] = 1
        current = 0
        X = 0
        for s in S:
            current = (current + int(s) * 10 ** X) % P
            ans += mod[current]
            mod[current] += 1
            X += 1
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    N, P = map(int, input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        D = [0] * N
        A = [0] * (N + 1)
        for i, s in enumerate(S):
            D[i] = int(s) * 10 ** i % P
            if i == 0:
                A[i] = D[i]
            else:
                A[i] = (D[i] + A[i - 1]) % P
        c = collections.Counter(A)
        ans = sum([i * (i - 1) // 2 for i in c.values()])
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from copy import deepcopy 

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

zero = np.zeros(p,dtype = int) #動的計画法
dp = deepcopy(zero)

count = 0
d = 1
for i in range(n): #1の位から順に数を追加していく
    ne_ar = deepcopy(zero)
    if(p == 2 or p == 5): #10と互いに素ではない場合
        ne = int(s[n-i-1]) % p
        if(ne == 0):
            dp[0] += 1
        count += dp[0] #
    else:
        ne = (int(s[n-i-1]) * d) % p #10とは互いに素なので、sと同じ位で考えて良い
        ne_ar[ne:] += dp[:(p-ne)] #新しく追加する数の余りをずらす
        ne_ar[:ne] += dp[(p-ne):]
        ne_ar[ne] += 1 #新しい数のみの時
        dp = ne_ar
        d *= 10
        d %= p
        count += ne_ar[0] #neを一番上の位とする部分集合の数を足す

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros(p,dtype = int)

count = 0
d = 1
for i in range(n):
    ne_ar = np.zeros(p,dtype = int)
    if(p == 2 or p == 5):
        ne = int(s[n-i-1]) % p
        if(ne == 0):
            dp[0] += 1
        count += dp[0]
    else:
        ne = (int(s[n-i-1]) * d) % p
        ne_ar[ne:] += dp[:(p-ne)]
        ne_ar[:ne] += dp[(p-ne):]
        ne_ar[ne] += 1
        dp = ne_ar
        d *= 10
        d %= p
        count += ne_ar[0]

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, p = [int(_) for _ in 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)
    exit()

t = [0 for i in range(n+1)]
P = [0 for i in range(p)]
P[0] += 1
for i in range(1, n+1):
    t[i] = (t[i-1]+int(s[n-i])*10**i) % p
    P[t[i]] += 1

ans = 0
for c in P:
    ans += c*(c-1)//2
# print(t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
s=input()
d = defaultdict(int)
ans = 0
if p ==2 or p==5:
    for i, x in enumerate(s):
        if int(x)%p==0:
            ans += i+1
    print(ans)

else:
    for i in range(n):
        x = int(s[i:])%p
        d[x]+=1
    for i in d:
        ans += d[i]*(d[i]-1)//2
        
    print(ans + d[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
s=input()
d = defaultdict(int)
ans = 0
if p ==2 or p==5:
    for i, x in enumerate(s):
        if int(x)%p==0:
            ans += i+1
    print(ans)

else:
    for i in range(n):

        x = s[i:]

        

        d[int(x)%p]+=1
    for i in d:
        ans += d[i]*(d[i]-1)//2
        
    print(ans + d[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
s=input()
d = defaultdict(int)
ans = 0
if p ==2 or p==5:
    for i, x in enumerate(s):
        if int(x)%p==0:
            ans += i+1
    print(ans)

else:
    for i in range(n):

        x = s[i:]

        while x[0]=="0" :
            if len(x) == 1:
                break
            x = x[1:]

        d[int(x)%p]+=1
    for i in d:
        ans += d[i]*(d[i]-1)//2
        
    print(ans + d[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = int(S)
    primdic = defaultdict(int)
    for i in range(1,N+1):
        # i~右端までの数字のmodPをキーにする
        primdic[(S%pow(10,i))%P] += 1
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-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==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = int(S)
    primdic = defaultdict(int)
    for i in range(1,N+1):
        # i~右端までの数字のmodPをキーにする
        primdic[(S%(10**i))%P] += 1
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-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==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    primdic = defaultdict(int)
    for i in range(N):
        # i~右端までの数字のmodPをキーにする
        primdic[int(S[i:])%P] += 1
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-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==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    #primdic = defaultdict(int)
    primdic = [0]*P
    for i in range(N):
        # i~右端までの数字のmodP
        primdic[int(S[i:])%P] += 1
    primdic[0] += 1
    ans = 0
    #for value in primdic.values():
    #    ans += value*(value-1)//2
    for value in primdic:
        ans += value*(value-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==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    primdic = defaultdict(int)
    for i in range(N):
        primdic[int(S[i:])%P] += 1
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int,input().split())
S = str(input())
L = len(S)
ans = 0
dic = {0:1} #一番右端は0なのでこれは常に必要
now = 0
if P == 2 or P == 5:
  kotae = 0
  for i in range(L):
    if int(S[L-1-i])%P == 0:
      kotae += L-i
  print(kotae)
  exit(0)
else:
  for i in range(L):
    now += int(S[L-1-i])*pow(10,i)
    temp = now%P
    if temp not in dic:
      dic[temp] = 1
    else:
      dic[temp] += 1
#print(dic)
ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

ls = [0]*P
ans = 0

if P == 2 or P == 5:
    for i in range(N):
        if int(S[i])%P == 0:
            ans += i+1
else:
    for i in reversed(range(N)):
        n = int(S[i:]) % P
        ans += ls[n]
        ls[n] += 1
        if n == 0:
            ans += 1
        

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    fac = 1
    for i in range(n-1, -1, -1):
        dp[i] = (dp[i + 1] + int(s[i]) * fac) % p
        fac *= 10 % p

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += v * (v - 1) // 2

print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    fac = 1
    for i in range(n-1, -1, -1):
        dp[i] = (dp[i + 1] + int(s[i]) * fac) % p
        fac *= 10

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += v * (v - 1) // 2

print(total)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        ints = 0
        power = 1
        for s in S[::-1]:
            ints += int(s) * power
            r = ints % P
            rcounts[r] += 1
            power *= 10
        c = 0
        for v in rcounts:
            c += v*(v-1)//2
        return c
    print(solve(N, P, S))

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        ints = 0
        for i, s in enumerate(S[::-1]):
            ints += int(s) * pow(10, i)
            r = ints % P
            rcounts[r] += 1
        c = 0
        for v in rcounts:
            c += v*(v-1)//2
        return c
    print(solve(N, P, S))

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        for i in range(len(S)):
            s = int(S[i:N])
            r = s % P
            rcounts[r] += 1
        c = 0
        for v in rcounts:
            if v > 1:
                c += v*(v-1)//2
        return c
    print(solve(N, P, S))

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        dicmodp = {}
        dicmodp[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        for i in range(len(S)):
            s = int(S[i:N])
            r = s % P
            dicmodp.setdefault(r, 0)
            dicmodp[r] += 1
        c = 0
        for k, v in dicmodp.items():
            if v > 1:
                c += v*(v-1)//2
        return c
    print(solve(N, P, S))

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    c = 0
    for i in range(N-1, -1, -1):
        if int(S[i]) % P == 0:
            # 以降桁を増やしてもOK
            c += i+1
    print(c)
else:
    dicmodp = {}
    dicmodp[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
    for i in range(len(S)):
        s = int(S[i:N])
        r = s % P
        dicmodp.setdefault(r, 0)
        dicmodp[r] += 1
    c = 0
    for k, v in dicmodp.items():
        if v > 1:
            c += v*(v-1)//2
    print(c)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    c = 0
    for i in range(N-1, -1, -1):
        if int(S[i]) % P == 0:
            # それ以降桁を増やしてもOK
            c += i+1
    print(c)
else:
    S = [int(S[i:N]) for i, s in enumerate(tuple(S))]

    dicmodp = {}
    dicmodp[0] = 1
    for s in S:
        r = s % P
        dicmodp.setdefault(r, 0)
        dicmodp[r] += 1
    c = 0
    for k, v in dicmodp.items():
        if v > 1:
            c += v*(v-1)//2
    print(c)

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+1, N+1):
        s = S[i:j]
        c += (int(s) % P == 0)
print(c)

Submission status: Time Limit Exceeded

Solution code:





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


"""
たとえばSが 123456789 だとすると
3456 = (3456789 - 789) // 1000
と表せる。
これがPで割り切れる場合、基本的には 3456789 と 789 がPで割り切れるとよい。
これはPと 10**x が互いに素の場合。
なので、10**x とPが互いに素の場合は、
・S[l:]をPで割った時余りがXXXになるものが何個、という情報を、Sの右端から集めていく。ただし、
・あるindexのlのS[l:]を見ているときに、その部分をPで割って余りがKになるなら、そのlに対してlより右にあるrについて、
　S[r:]をPで割った余りがKになるようにrを選んでS[l:r]を作ると、Pで割り切れる数字が得られる。その時点でのmod P = Kの個数に対応する。
　ただし、rに何も選ばない場合（lから端までを数字にする場合）もあるので、これも考慮に入れる。

Pが10と互いに素でない場合は、2と5がありうる。
これについて、それぞれ末尾が2の倍数か5の倍数であれば割り切れるので、
Sを左から見ていって、その数字が見つかれば、そのindexをふくむ左の位置で数字を作ればPで割れる数字ができる
"""

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

else:
    mod_P = [0] * P
    mod_P[0] += 1

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

print(ans)

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
  for i in range(len(s)):
    if int(s[i])%p == 0:
      count += i+1
  print(int(count))
else:
  premodlist = [int(s[i:n]) for i in range(n)]
  modset = [0]*p
  modset[0] += 1
  for i in premodlist:
    modset[i%p] += 1
  for i in modset:
    count += i*(i-1)/2
  print(int(count))

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
  for i in range(len(s)):
    if int(s[i])%p == 0:
      count += i+1
  print(int(count))
else:
  premodlist = [int(s[i:n]) for i in range(n)]
  modlist = list(map(lambda x: x%p, premodlist))
  modlist.append(0)
  modset = list(set(modlist))
  for i in modset:
    m = modlist.count(i)
    count += m*(m-1)/2
  print(int(count))

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
  for i in range(len(s)):
    if int(s[i])%p == 0:
      count += i+1
  print(int(count))
else:
  modlist = []
  for i in range(len(s)):
    modlist.append(int(s[i:n])%p)
  modlist.append(0)
  modset = list(set(modlist))
  for i in modset:
    m = modlist.count(i)
    count += m*(m-1)/2
  print(int(count))

Submission status: Time Limit Exceeded

Solution code:
# ABC158E
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:

import numpy as np
n,p = map(int,input().split(" "))

tmp = input()
s = [int(c) for c in tmp]

res = 0
if p==2 or p==5:
    for i,v in enumerate(s):
        if v%p==0: res+=i+1
else:
    tens = np.zeros(n,dtype=np.int32)
    tens[0] = 1
    for i in range(n-1):
        tens[i+1] = (tens[i] * 10)%p
    tens = tens[::-1]
    
    sum = 0
    cnt = np.zeros(p,dtype=np.int32)
    cnt[0] = 1
    for i,v in enumerate(s):
        sum = (sum + v*tens[i]) % p
        res += cnt[sum]
        cnt[sum] += 1

print(res)