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()
count = 0
for i in range(n):
    for j in range(1, n - i + 1):
        num = int(s[i: i + j])
        if num % p == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

a = [0] * (N + 1)
r = [0] * P

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = (int(S[N-i])*tenfactor+a[i-1])
        tenfactor*=10
        r[a[i] % P] += 1
    r[0] += 1
    ans = 0
    from collections import Counter
    C=Counter(r)
    for v,i in C.items():
        ans += (v * (v - 1) // 2)*i
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)

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

Submission status: Time Limit Exceeded

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

a = [0] * (N + 1)
r = [0] * P

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = (int(S[N-i])*tenfactor+a[i-1])
        tenfactor*=10
        r[a[i] % P] += 1
    r[0] += 1
    ans = 0
    for i in range(P):
        ans += r[i] * (r[i] - 1) // 2
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)

Submission status: Time Limit Exceeded

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

a = [0] * (N + 1)
r = [0] * P

if P != 2 and P != 5:
    tenfactor=1
    for i in range(1,N+1):
        a[i] = (int(S[N-i])*tenfactor+a[i-1])
        tenfactor*=10
        r[a[i] % P] += 1
    r[0] += 1
    ans = 0
    for i in range(P):
        ans += r[i] * (r[i] - 1) // 2
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i + 1
elif P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i + 1

print(ans)

Submission status: Time Limit Exceeded

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

a=[0]*(N+1)
r=[0]*P

if P!=2 and P!=5:
    for i in range(N):
        a[i] = int(S[i:])
        temp=a[i]%P
        r[temp]+=1
    r[0]+=1
    ans=0
    for i in range(P):
        ans+=r[i]*(r[i]-1)//2
elif P==2:
    ans=0
    for i in range(N):
        if int(S[i])%2==0:
            ans+=i+1
elif P==5:
    ans=0
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            ans+=i+1

print(ans)

Submission status: Time Limit Exceeded

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

a=[0]*(N+1)
r=[0]*P

if P!=2 and P!=5:
    for i in range(N):
        a[i] = int(S[i:])
    for i in range(N+1):
        temp=a[i]%P
        r[temp]+=1
    ans=0
    for i in range(P):
        ans+=r[i]*(r[i]-1)//2
elif P==2:
    ans=0
    for i in range(N):
        if int(S[i])%2==0:
            ans+=i+1
elif P==5:
    ans=0
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            ans+=i+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=int(input())
def ds(m):
  t=0
  while m>0:
    m=m//10
    t=t+1
  return t	

n=S
lists=[]
b=range(ds(n))
for a in b:
  lists.append(n%10)
  n=n//10

u=0
for j in b:
  s=0
  for i in range(j,ds(S)):
    s=lists[i]*10**(i-j)+s
    if s%P==0:
      u=u+1
    
print(u)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * (10**(n-i) % p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	def power(x, y):
		if y == 0:
			return 1
		elif y == 1:
			return x
		elif y % 2 == 0:
			return power(x, int(y/2)) ** 2 % P
		else:
			return power(x, int((y-1)/2)) ** 2 * x % P

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

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		for i, s in enumerate(S[::-1]):
			tmp += power(10, i) * s
			mod_cnt[tmp%P] += 1
			tmp %= P
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



def main():
	N, P = MAP()
	S = list(map(int, list(input())))

	def power(x, y):
		if y == 0:
			return 1
		elif y == 1:
			return x
		elif y % 2 == 0:
			return power(x, int(y/2)) ** 2 % P
		else:
			return power(x, int((y-1)/2)) ** 2 * x % P

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

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		for i, s in enumerate(S[::-1]):
			tmp += power(10, i) * s
			mod_cnt[tmp%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s*=10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, P = MAP()
	S = input()

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

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = ""

		mod_cnt = [0]*P

		for i, s in enumerate(S[::-1]):
			tmp = s + tmp
			mod_cnt[int(tmp)%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n,p = map(int,input().split())
	s = [int(c) for c in list(input().strip())][::-1]
	num = 0
	ans = 0
	if p == 2 or p == 5:
		for i in range(n):
			if s[i]%p == 0:
				ans += n-i
		print(ans)
		return
	arr = [0]*p
	arr[0]=1
	z = 1
	t = 0
	for ss in s:
		t = (t + z*ss)%p	
		z *=10 %p
		arr[t] += 1
	for l in arr:
		ans += l * (l - 1) // 2
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

	for i, s in enumerate(S):
		if int(s)%P == 0:
			ans += i+1
	print(ans)

else:
	tmp = ""

	mod_dic = defaultdict(int)

	for i, s in enumerate(S[::-1]):
		tmp = s + tmp
		mod_dic[int(tmp)%P] += 1
	ans = 0
	for v in mod_dic.values():
		ans += v*(v-1)//2
	print(ans+mod_dic[0])

Submission status: Time Limit Exceeded

Solution code:
def main():
	n,p = map(int,input().split())
	s = [int(c) for c in list(input().strip())]
	s = s[::-1]
	num = 0
	ans = 0
	if p == 2 or p == 5:
		for i in range(n):
			if s[i]%p == 0:
				ans += n-i
		print(ans)
		return
	arr = [0]*p
	arr[0]=1
	z = 1
	t = 0
	for ss in s:
		t = (t + z*ss)%p	
		z *=10 %p
		arr[t] += 1
	for l in arr:
		ans += l * (l - 1) // 2
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    P_list = np.zeros(P)
    P_list[0] = 1

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

    else:
        ans = 0
        Uj = 0
        for i in range(N-1, -1, -1):
            Uj = Uj + int(S[i])*10**(N-i-1)
            amari = Uj%P
            ans = ans + P_list[amari]
            P_list[amari] += 1

        ans = int(ans)

        print ans
        exit()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

count=0
for i in range(1,n+1):
    for j in range(n-i+1):
        a=s[j:j+i]
        a="".join(a)
        a=int(a)
        if a%p==0:
            count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
	n,p = map(int,input().split())
	s = [int(c) for c in input()][::-1]
	num = 0
	ans = 0
	if p == 2 or p == 5:
		for i in range(n):
			if s[i]%p == 0:
				ans += n-i
		print(ans)
		return
	arr = [0]*p
	arr[0]=1
	z = 1
	t = 0
	for ss in s:
		t = (t + z*ss)%p	
		z *=10 %p
		arr[t] += 1
	for l in arr:
		ans += l * (l - 1) // 2
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n,p = map(int,input().split())
	s = [int(c) for c in input()] 
	num = 0
	ans = 0
	if p == 2 or p == 5:
		for i in range(n):
			if s[i]%p == 0:
				ans += i+1	
		print(ans)
		exit()
	arr = [0]*p
	s = s[::-1]
	arr[0]=1
	z = 1
	t = 0
	for ss in s:
		t = (t + z*ss)%p	
		z *=10 %p
		arr[t] += 1
	for l in arr:
		ans += l * (l - 1) // 2
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = [int(c) for c in input()] 
num = 0
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		if s[i]%p == 0:
			ans += i+1	
	print(ans)
	exit()
arr = [0]*p
s = s[::-1]
z = 1
t = 0
for ss in s:
	t = (t + z*ss)%p	
	z *=10 %p
	#print(t)
	arr[t] += 1
arr[0]+=1
for l in arr:
	ans += l * (l - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

P_list = np.zeros(P)
P_list[0] = 1
ans = 0

for i in range(N-1, -1, -1):
    Uj = int(S[i:N])
    amari = Uj%P
    ans = ans + P_list[amari]

    P_list[amari] += 1

ans = int(ans)

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

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



print ans

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = [int(c) for c in input()] 
num = 0
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		if s[i]%p == 0:
			ans += i+1	
	print(ans)
	exit()
arr = [0]*p
s = s[::-1]
z = 1
t = 0
for ss in s:
	t = (t + z*ss)%p	
	z *=10 %p
	#print(t)
	arr[t] += 1
arr[0]+=1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
arr = [0]*p
s = s[::-1]
z = 1
t = 0
for ss in s:
	t = (t + z*int(ss))%p	
	z *=10 %p
	#print(t)
	arr[t] += 1
arr[0]+=1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, P = map(int, input().split())
S = [int(s) for s in input()]
S.reverse()

ans = 0

if P != 2 and P != 5:
    S = [(s * 10**n) % P for n, s in enumerate(S)]
    for n in range(1, N):
        S[n] = (S[n-1] + S[n]) % P

    S = Counter(S)
    for p in range(P):
        if p == 0:
            ans += S[p]
        ans += (S[p] * (S[p]-1)) // 2

else:
    for n in range(N):
        if S[n] % P == 0:
            ans += N - n

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
	n,p = map(int,input().split())
	s = input()
	num = 0
	s1 = [0]*(n+1)
	ans = 0
	if p == 2 or p == 5:
		for i in range(len(s)):
			if int(s[i])%p == 0:
				ans += i+1	
		print(ans)
		return
	ans = 0
	arr = [0]*p
	s = s[::-1]
	z = 1
	for i in range(n):
		s1[i+1] = s1[i] + int(s[i])*z
		z *=10 %p
		s1[i+1] %=p
		arr[s1[i]] += 1
	arr[s1[n]]+=1
	#print(s1)
	for i in range(p):
		ans += arr[i] * (arr[i] - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
z = 1
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*z
	z *=10 %p
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1
#print(s1)
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*10**i
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
count = 0
for left in range(N):
    for right in range(1, N+1):
        if left < right:
            if int(S[left:right]) % P == 0:
                count += 1
print(count)

Submission status: Time Limit Exceeded

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

# process
ans = 0
for i in range(N-1):
    mod = S[i]%P
    if mod == 0:
        ans += 1
    pmod = mod

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

if S[-1]%P == 0:
    ans += 1

# output
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    for i in range(N-1, -1, -1):
        n = int(S[i:])
        mod = n % P
        ans += ct[mod]
        ct[mod] += 1
print(ans)

Submission status: Time Limit Exceeded

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

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C*=10
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        sArr = [0] * N
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                sArr[i - 1] = int(S[-1])%P
            else:
                sArr[i-1]  = (int(S[-i])*C + sArr[i-2])%P
            counts[sArr[i-1]]+=1
            C*=10
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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


def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        sArr = [0] * N
        C = 1
        counts = [0] * P
        for i in range(1,N+1):
            if i == 1:
                sArr[i - 1] = int(S[-1])%P
            else:
                sArr[i-1]  = (int(S[-i])*C + sArr[i-2])%P
            counts[sArr[i-1]]+=1
            C*=10
        sum = 0
        for c in counts:
            if c == 0:
                continue
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

    # sum = 0
    # for i in range(N):
    #     sDiv = 0
    #     coeff = 1
    #     for j in range(i,N):
    #         sDiv= (sDiv*coeff + arr[j])%P
    #         coeff*=10
    #         if sDiv == 0:
    #             sum+=1
    # print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            count += i+1
else:
    u = [0]*(n+1)
    for i in range(n):
        u[i] = int(s[i:])%p
    a = Counter(u).values()
    for i in list(a):
        count += i*(i-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 k in range(i,N):
        X=int(S[i:k+1])
        if X%P==0:
            count+=1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, P = list(map(int, input().split()))
S = input()
ans = 0
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=(i+1)
else:
    a = {0:[N]}
    for i in range(N):
        mod = int(S[N-i-1:])%P
        if mod in a:
            ans+=len(a[mod])
        else:
            a[mod] = []
        a[mod].append(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
for i in range(n+1):
	s1[i] = int(s)%(10**i)%p
	arr[s1[i]] += 1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

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

tot = 0

if P in [2,5]:
  for i in range(1,N+1):
    if int(S[-i]) % P == 0:
      tot += N-i+1
else:
  S_mod = [0] * P
  S_mod[0] = 1 # 0 = 0 mod P
  for i in range(N-1, -1, -1):
    mod = int(S[i:]) % P
    #print(S[i:], mod)
    tot += S_mod[mod]
    S_mod[mod] += 1
print(tot)

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
for i in range(n+1):
	s1[i] = int(s)%(10**i)%p
arr = [0]*p
for i in range(n+1):
	arr[s1[i]] += 1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, P = (int(i) for i in input().split())
S = input()

ans = 0
if P == 5 or P == 2:
    for j in range(1, N+1):
        # j文字取る
        num = int(S[:j])
        if num % P == 0:
            ans += j
else:
    acc = [0]*(N+1)
    d = 1
    for i, s in enumerate(S[::-1], start=1):
        # print(i, s)
        acc[i] = (int(s) * d + acc[i-1]) % P
        d *= 10
        d %= P
    c = Counter(acc)
    # print(acc, c)
    ans = sum(v*(v-1)//2 for v in c.values())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (int(s) * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline
    N, P = (int(i) for i in input().split())
    S = [int(i) for i in input().rstrip().decode()]

    ans = 0
    if P == 5 or P == 2:
        S = "".join([str(s) for s in S])
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1]):
            # print(i, s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        S = [s for s in S]
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1]):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1]):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.readline
    N, P = (int(i) for i in input().split())
    S = input().rstrip()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += len(S[:j])
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1]):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()