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
from bisect import bisect_left

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)

Submission status: Time Limit Exceeded

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

slist=list(S)
count=0

alldict=dict()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr



def ngram(s,n,N,P):
    count=0
    for i in range(N):
        if i + n > N:
            return count
        
        #result.append(s[i: i+n])
        a=int(s[i:i+n])
        if(a in alldict):
            if(alldict[a]==True):
                count+=1
                continue
            else:
                continue
        else:
            if(a%P==0):
                count+=1
                alldict[a]=True
            else:
                alldict[a]=False
        #print(s[i:i+n])
    return count


for i in range(1,len(S)+1):
    count+=ngram(S,i,n,P)

print(count)

Submission status: Time Limit Exceeded

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

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()))
from collections import deque, defaultdict
def resolve():
    N, P = lr()
    S = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = defaultdict(int)
    S = deque(S)
    for i in range(N):
        lp[int(''.join(S))%P] += 1
        S.popleft()
    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:

N, P = input().split()
p_len = len(P)
N = int(N)
P = int(P)

S = input()

cnt = 0

if P in [2,5]:
    for i in range(N):
        cnt += i+1 if int(S[i]) % P == 0 else 0
else:
    for l in range(1, N+1):
        for i in range(N+1-l):
            cnt += 1 if int(S[i:i+l]) % P == 0 else 0
print(cnt)

Submission status: Time Limit Exceeded

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

def nC2(n):
    if n == 0:
        return 0
    return n*(n-1)//2

if p != 2 and p != 5:
    u = []
    for i in range(n):
        u.append(int(s[i:])%p)
    onaji = {}
    for i in u:
        if not i in onaji:
            onaji[i] = 1
        else:
            onaji[i] += 1
    ans = 0
    for key, r in onaji.items():
        ans += nC2(r)
        if key == 0:
            ans += r
    print(ans)

elif p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0,2,4,6,8]:
            ans += i+1
    print(ans)

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

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = list(input())
mod = P
dp = [[0 for i in range(N-j)] for j in range(N)]
dp
for j in range(N):
    dp[j][0]=(int(S[j])%mod)
    for i in range(1,N-j):
        dp[j][i]=((dp[j][i-1]*10+int(S[j+i]))%mod)
ans = 0
for i in range(N):
    ans += dp[i].count(0)
    
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()))
from collections import deque
def resolve():
    N, P = lr()
    S = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    S = deque(S)
    for i in range(N):
        lp[int(''.join(S))%P] += 1
        S.popleft()
    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:
from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    for i in range(1, len(s)+1):
        m[int(s[-i:]) % p] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())

Submission status: Time Limit Exceeded

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

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.count(mod)
        l.append(mod)
        if mod==0:
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

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
  for i in range(1,n):
    sp[n-i-1] = (sp[n-i]+s[n-i-1]*(10**i%p))%p
  cj = sp.count(0)
  ans += int(cj*(cj+1)/2)
  for j in range(1,p):
      cj = sp.count(j)
      ans += int(cj * (cj-1)/2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    for i in range(n):
        s+=int(S[-(i+1)])*(10**i)
        a=s%p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: 
            res += i+1
    print(res)
    quit()
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)

Submission status: Time Limit Exceeded

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

ans=0
for j in range(n):
  ans+=dp[j][0]




print(ans)
#print(dp)

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
    for i in range(N)[::-1]:
        x = S[i] * 10**(N-i-1) + U[i+1]
        U[i] = (S[i] * 10**(N-i-1) + U[i+1]) % P
        ans += count[U[i]]
        count[U[i]] += 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 = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 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:
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=[0]*p
    s=0
    for i in range(n):
        s+=int(S[-(i+1)])*(10**i)
        a=s%p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#####

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

#####

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


from sys import stdin
import sys

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


def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	ans=0
	if p%2==0 or p%5==0:
		for i0 in range(len(s)-1,-1,-1):
			sub=int(s[i0:i0+1])
			if sub%p==0:
				ans+=i0+1
	else:
		numP0=np.zeros(p, int32)
		numP0[0]=1
		for i0 in range(len(s)-1,-1,-1):
			sub=s[i0:]
			sub=int(sub)
			sub%=p
			ans+=numP0[sub]
			numP0[sub]+=1
# 			print(s[i0:], sub, numP0, ans)
	print(ans)
		

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

    if P == 5 or P == 2:
        cnt = 0
        for j in range(N - 1, -1, -1):
            if SI[j] % P == 0:
                cnt += j + 1
        print(cnt)
        exit()

    cnt = 0
    di = 10

    for j in range(N - 1, -1, -1):
        n = SI[j]

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

    print(cnt)


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
    for i, c in enumerate(map(int, s)):
        k = (c * (10**i) + k) % p
        cnt[k] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: res += i+1
    print(res)
    quit()
now = 0
d = defaultdict(int)
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i)
    now %= p
    # print(now)
    d[now] += 1
for key in list(d):
    v = d[key]
    res += v*(v-1)//2
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import lil_matrix

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

mtxs = []
for i in range(10):
    mtx = lil_matrix( (P, P), dtype=np.int64 )
    for j in range(P):
        mtx[j, (j * 10 + i) % P] += 1
    mtxs.append(mtx)

mod = np.zeros(P, dtype=np.int64)
ans = 0
for i in range(N):
    last = int(S[i])
    mod = mod * mtxs[last]
    mod[last % P] += 1
    ans += mod[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: res += i+1
    print(res)
    quit()
now = 0
d = defaultdict(int)
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i)
    # print(now)
    d[now%p] += 1
for key in list(d):
    v = d[key]
    res += v*(v-1)//2
print(res)

Submission status: Time Limit Exceeded

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

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

else:
    data = [0] * P
    s = int(S)
    for i in range(N):
        data[s%P] += 1
        s -= int(S[i]) * (10**(N-i-1))
    #print(data)
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
n,p = na()
s = ns()
s = list(map(int, s))
ans = 0

if p == 2:
	for i in range(n):
		if s[i]%2 == 0:
			ans += i+1
	print(ans)
	exit()
if p == 5:
	for i in range(n):
		if s[i]%5 == 0:
			ans += i+1
	print(ans)
	exit()
 
seenRemainders = [set() for k in range(n)] #長さn
for i in range(n):
    remainder = 0
    prefixesFound = 0
    for j in range(i,n):
        remainder = (10 * remainder + s[j]) % p
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].add(remainder)
        if remainder == 0:
            prefixesFound+=1
    ans += prefixesFound * (prefixesFound + 1) // 2
 
print(ans)

Submission status: Time Limit Exceeded

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

con = 0

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

print(con)

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 = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    MOD = 10**9+7
    SIZE = 2*10**5+1
    inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0]*SIZE  # fac[j] = j! mod MOD
    finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2,SIZE):
        inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
        fac[i] = fac[i-1]*i%MOD
        finv[i]= finv[i-1]*inv[i]%MOD
    
    def choose(n,r): # nCk mod MOD の計算
        if 0 <= r <= n:
            return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
        else:
            return 0
    ans = lp[0]
    for i in range(P):
        ans += choose(lp[i], 2)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

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

slist=list(S)
count=0

def ngram(s,n,N,P):
    count=0
    for i in range(N):
        if i + n > N:
            return count
        #result.append(s[i: i+n])
        if(int(s[i:i+n])%P==0):
            count+=1
        #print(s[i:i+n])
    return count

smap=[]
for i in range(1,len(S)+1):
    #smap+=ngram(S,i)
    count+=ngram(S,i,n,P)
#smap1=set(smap)
#print(smap)

#count=0
#for i in smap:
#    if(int(i)%P==0):
        #print(i)
#        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
S=input()
s=int(S)
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=[0]*p
    for i in range(n):
        a=int(S[-i:])
        a%=p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Submission status: Time Limit Exceeded

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

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

else:
    data = [0] * P
    for i in range(N):
        data[int(S[i:])%P] += 1
    #print(data)
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

print(ans)

Submission status: Time Limit Exceeded

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

count=0
c_zero=1
for i in range(N):
    tmp=0
    flag=0
    for j in range(i,N):
#         print(int(S[i:j+1]),int(S[i:j+1])%P,c_zero)
        if int(S[i])==0:
            count+=c_zero
            c_zero+=1
            flag=1
            break
        else:
            if int(S[i:j+1])%P==0:
                tmp+=1
    count+=tmp*c_zero
#     print(count)
    if flag==0:
        c_zero=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, p = map(int, input().split())
s = input()
no_dict = {}
count = 0
for i in range(0, n):
    for j in range(i+1, n+1):
        if s[i:j] in no_dict:
            if no_dict[s[i:j]] == 100:
                count += 1
        else:
            if int(s[i:j]) % p == 0:
                no_dict[s[i:j]] = 100
                count += 1
            else:
                no_dict[s[i:j]] = 1
print(count)

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 = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    MOD = 10**9+7
    SIZE = 10**6+1
    inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0]*SIZE  # fac[j] = j! mod MOD
    finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2,SIZE):
        inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
        fac[i] = fac[i-1]*i%MOD
        finv[i]= finv[i-1]*inv[i]%MOD
    
    def choose(n,r): # nCk mod MOD の計算
        if 0 <= r <= n:
            return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
        else:
            return 0
    ans = lp[0]
    for i in range(P):
        ans += choose(lp[i], 2)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
N,P=[int(i) for i in input().split()]
S = str(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:
    modlist = [0 for i in range(P)]

    for i in range(1,N+1):
        n = int(S[N-i:])
        modlist[n%P] = modlist[n%P]+1
    modlist[0]+=1

    ans=0
    for i in modlist:
        if i>=2:
            ans = ans + i*(i-1)/2
    print(int(ans))

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, p, s):
    res = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p == 0:
                res += i + 1
        return res

    mod_count = [0] * p
    temp = 0
    for i in range(n):
        temp = (temp + 10 ** i * int(s[-(i + 1)])) % p
        mod_count[temp] += 1
    res += mod_count[0]
    for i in range(p):
        res += mod_count[i] * (mod_count[i] - 1) // 2
    return res


def main():
    n, p = map(int, input().split())
    s = input()
    res = solve(n, p, s)
    print(res)


def test():
    assert solve(4, 3, "3543") == 6
    assert solve(4, 2, "2020") == 10
    assert solve(20, 11, "33883322005544116655") == 68


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in tuple(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    d=defaultdict(int)
    tmp=0
    ans=0
    for i,s in enumerate(reversed(S)):
        tmp+=s*pow(10,i)
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Time Limit Exceeded

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

slist=list(S)

def ngram(s,n):
    result = []
    for i in range(len(s)):
        if i + n > len(s):
            return result
        result.append(s[i: i+n])
        #print(s[i:i+n])
    return result

smap=[]
for i in range(1,len(S)+1):
    smap+=ngram(S,i)

#smap1=set(smap)
#print(smap)

count=0
for i in smap:
    if(int(i)%P==0):
        #print(i)
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

    print(ans)

else:
    li = [0]
    for i, e in enumerate(s[::-1], 1):
        li.append((li[-1] + int(e) * 10 ** i) % p)

    c = Counter(li)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in list(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    S.reverse()
    d=defaultdict(int)
    tmp=0
    ans=0
    for i,s in enumerate(S):
        tmp+=s*pow(10,i)
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

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 = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    from functools import reduce
    def Comb(N, A):
        num = reduce(lambda x, y: x * y, range(N, N-A, -1))
        den = reduce(lambda x, y: x * y, range(1, A+1))
        return num//den
    ans = lp[0]
    for i in range(P):
        ans += Comb(lp[i], 2)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

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

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

else:
    data = [0] * P
    S = "".join(list(map(str,S)))
    for i in range(N):
        data[int(S[i:])%P] += 1
    #print(data)
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

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

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

    ans = 0
    d[0] = 1
    for i in range(N-1, -1, -1):
        # print(S[i:])
        v = int(S[i:])
        if v % P in d:
            ans += d[v % P]
        d[v % P] =  d.get(v % P, 0) + 1
    return ans

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

Submission status: Time Limit Exceeded

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

def main():
    N,P = map(int,input().split())
    s = input()
    l = len(s)
    ans = 0
    if 10%P == 0:
        for i,st in enumerate(s[::-1]):
            num = int(st)
            if num%P == 0:
                ans += l-i
    else:
        d = defaultdict(int)
        d[0] = 1
        now = ""
        for st in s[::-1]:
            now = st+now
            num = int(now)
            ans += d[num%P]
            d[num%P] += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
# l = list(map(lambda x: int(x)%p, list(input())))
l = input()

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

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def S(): return input().rstrip()


def main():
    N, P = MI()
    s = S()
    c = 0
    for i in range(N):
        for j in range(i+1, N+1):
            s_ = s[i:j]
            if int(s_)%P==0: c+=1
    print(c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

import glob

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\158\\E'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'


class Common:
    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index - 1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        tmp = self.input_data().split()
        N = int(tmp[0])
        P = int(tmp[1])
        S = self.input_data()

        count = 0

        amari = [0 for i in range(N)]

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


        print(str(count))


solver = Solver(REL_PATH)
solver.exec_resolve()