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: Wrong Answer

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

a = [0]
for c in S:
    c = int(c)
    a.append((a[-1]*10+c) % P)

if P in (2,5,10):
    ans = 0
    for i,b in enumerate(a):
        if b: continue
        ans += i
    print(ans)
else:
    from collections import Counter
    ctr = Counter(a)
    ans = 0
    for k,v in ctr.items():
        ans += v*(v-1)//2
    print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
pr = [0 for _ in range(p)]
pr[0] = 1
now = 0
s = input()
ten = [1]
for i in range(n-1):
  ten.append(ten[-1]*10%p)
ten.reverse()
#print(ten)
for i in range(n):
  now *= 10
  now += int(s[i])
  now %= p
  tmp = int(now)
  tmp *= ten[i]
  tmp %= p
  pr[tmp] += 1
#print(pr)
ans = 0
for x in pr:
  ans += x * (x-1)
ans //= 2
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
a = [1]
for i in range(n - 1):
    a.append(a[-1] * 10 % p)
a.reverse()
b = [int(s[i]) * a[i] % p for i in range(n)]
c = [0]
for i in range(n):
    c.append((c[-1] + b[i]) % p)
d = {}
for i in c:
    d.setdefault(i, 0)
    d[i] += 1
ans = 0
for i in d.values():
    ans += i * (i - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,P = inpl()
S = list(map(int,list(input())))

tmpl = [s*pow(10,N-1-i,P)%P for i,s in enumerate(S)]
xx = [tmpl[0]]
for t in tmpl[1:]:
    xx.append((xx[-1]+t)%P)

yy = [S[0]%P]
for s in S[1:]:
    yy.append((yy[-1]*10+s)%P)

nums = [0]*P
nums[0] += 1
ans = 0
for i,y in enumerate(yy):
    tmp = y*pow(10,N-1-i,P)%P
    ans += nums[tmp]
    nums[xx[i]] += 1


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int, input().split())
pt = [1]
for i in range(N):
  pt.append(pt[-1]*10%P)
S = [int(c)%P for c in input()]
dp = [(S[0]*pt[N-1])%P]
for i in range(1,N):
  dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

c = Counter(dp)
ans = sum(u*(u-1)//2 for u in c.values())
print(ans+c[0])

Submission status: Wrong Answer

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

S = input()

mods = []
d = 1
for s in reversed(S):
	mods.append(int(s) * d % P)
	d *= 10

counts = [0] * P
counts[0] = 1
h = 0
total = 0
for i, m in enumerate(mods):
	h += m
	total += counts[h % P]
#	print(i, m, counts[h % P])
	counts[h % P] += 1

print(total)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
if P != 2 and P != 5:
    p_array = [0] * P

    mod = 0
    for s in S:
        s = int(s)
        mod = (mod * 10 + s) % P
        p_array[mod] += 1

    ans = 0
    for i, p in enumerate(p_array):
        if i == 0:
            ans += p
            ans += (p * (p-1) // 2)

    print(int(ans))

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,P = inpl()
S = list(map(int,list(input())))

tmpl = [s*pow(10,N-1-i,P)%P for i,s in enumerate(S)]
xx = [tmpl[0]]
for t in tmpl[1:]:
    xx.append((xx[-1]+t)%P)

yy = [S[0]%P]
for s in S[1:]:
    yy.append((yy[-1]*10+s)%P)

nums = [0]*P
nums[0] += 1
ans = 0
for i,y in enumerate(yy):
    tmp = y*pow(10,N-1-i)%P
    ans += nums[tmp]
    nums[xx[i]] += 1


print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N, mod = map(int, input().split())
    S = input().rstrip('\n')

    M = [0] * N
    S = S[::-1]
    for i, s in enumerate(S):
        s = int(s)
        M[i] = (M[i-1] + (s * pow(10, i, mod))%mod)%mod
    M.reverse()
    M.append(0)
    C = Counter(M)
    ans = 0
    for x in C:
        ans += (C[x] * (C[x]-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(n):
    s[i] = int(s[i]) % p

ls = [0]

for i in range(n):
    tmp = ls[len(ls) - 1]
    ls.append((tmp * 10 + s[i]) % p)

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

for i in range(n + 1):
    ans += mp[ls[i]]
    mp[ls[i]] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
rem=[0]*n
cnt=[0]*p
s=input()[::-1]
kake=1
for i in range(n):
    rem[i]=rem[i-1]+int(s[i])*kake
    rem[i]%=p
    cnt[rem[i]]+=1
    kake*=10
    kake%=p
ans=0
for i in range(p):
    ans+=cnt[i]*(cnt[i]-1)//2
print(ans+cnt[0])

Submission status: Wrong Answer

Solution code:
n, p = map(int, raw_input().strip().split())
s = raw_input().strip()
n = len(s)
l = [0 for i in xrange(n)]

l[n - 1] = int(s[n - 1])
if l[n - 1] >= p: l[n - 1] %= p

p10 = 1
for i in xrange(n - 2, -1, -1):
    p10 *= 10
    if p10 >= p: p10 %= p
    l[i] = p10 * (ord(s[i]) - ord('0'))
    if l[i] >= p: l[i] %= p

cnt = [0 for i in xrange(p)]
cnt[l[0]] += 1
for i in xrange(1, n):
    l[i] += l[i - 1]
    if l[i] >= p: l[i] -= p

    cnt[l[i]] += 1

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

ans += cnt[0]

print ans

Submission status: Wrong Answer

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

rem_dict = {i: 0 for i in range(p)}

for i in range(n):
  rem = int(s[:i+1]) % p
  rem_dict[rem] += 1

ans = 0
ans += rem_dict[0]
for rem, num in rem_dict.items():
  ans += (num * (num  - 1)) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(reversed(list(map(int, input()))))
cur = 1
c = [0] * (n + 1)
ans = 0
t = [0] * p
t[c[0]] += 1
for i in range(n):
    c[i + 1] = (c[i] + cur * s[i]) % p
    ans += t[c[i + 1]]
    t[c[i + 1]] += 1
    cur = cur * 10 % p
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
ans = 0
if p == 2 or p == 5:
    if p == 2:
        ok = [0, 2, 4, 6, 8]
    else:
        ok = [0, 5]
    for i, c in enumerate(s):
        if int(c) in ok:
            ans += i+1
    print(ans)
    exit()

cum = [0] * (n+1)
keta = 1
for i, c in enumerate(s):
    cum[i+1] = cum[i] + keta * int(c)
    cum[i+1] %= p
    keta = (keta * 10) % p
counter = [0] * (p)
for c in cum:
    counter[c] += 1
ans = 0
for c in counter:
    ans += c * (c-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p = LI()
    s = list(map(int, input()))[::-1]
    if p in [2,5]:
        ans = (n*(n+1)) >> 1
        ans -= n
        for i in s:
            if i%p == 0:
                ans += 1
        print(ans)
        return
    a = [0]
    k = 10
    for i in range(n):
        si = s[i]
        a.append((a[-1]+si*k)%p)
        k *= 10
        k %= p
    ans = 0
    d = defaultdict(lambda : 0)
    for i in a:
        ans += d[i]
        d[i] += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
res = 0
cnt = [0]*p
for i in range(n):
    res = (res+int(s[-i-1])*pow(10, i, p))%p
    cnt[res]+=1
ans = 0
for c in cnt:
    ans+=c*(c-1)//2
ans+=cnt[0]
print(ans)

Submission status: Wrong Answer

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

a = [0]
for c in S:
    c = int(c)
    a.append((a[-1]*10+c) % P)

from collections import Counter
ctr = Counter(a)

ans = 0
for k,v in ctr.items():
    if P <= 10 and k: continue
    ans += v*(v-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
pr = [0 for _ in range(p)]
pr[0] = 1
now = 0
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()
for i in range(n):
  now += int(s[i])
  now %= p
  pr[now] += 1
  now *= 10
  now %= p
#print(pr)
ans = 0
for x in pr:
  ans += x * (x-1)
ans //= 2
print(ans)

Submission status: Wrong Answer

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

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

L=[0]
NOW=1
for i in range(N):
    L.append((L[-1]+int(S[N-i-1])*NOW)%P)
    NOW=NOW*10%P

from collections import Counter
C=Counter(L)
ANS=0

for i in range(N):
    ANS+=C[L[i]]-1
    C[L[i]]-=1
print(ANS)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()[::-1]
C = [0]*p
now = 0
for i in s:
  a = int(i)
  now = (10*now+a)%p
  C[now] += 1
ans = C[0]
now = 0
for i in s[:-1]:
  a = int(i)
  now = (10*now+a)%p
  C[now] -= 1
  ans += C[now]
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p = LI()
    s = list(map(int, input()))[::-1]
    if p in [2,5]:
        ans = (n*(n+1)) >> 1
        ans -= n
        for i in s:
            if i%p == 0:
                ans += 1
        print(ans)
        return
    a = [0]
    for i in s:
        a.append((a[-1]+i)*10%p)
    ans = 0
    d = defaultdict(lambda : 0)
    for i in a:
        ans += d[i]
        d[i] += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
C = [0] * P
C[0] = 1
X = []
ans = 0

if P == 2 or P == 5:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
    print(ans)
else:
    a = 0
    for s in S:
        a = (a * 10 + int(s)) % P
        ans += C[a]
        C[a] += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N, mod = map(int, input().split())
    S = input().rstrip('\n')

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        s = int(s)
        M[i] = (M[i-1] + (s * (10**i))%mod)%mod
    C = Counter(M)
    ans = 0
    for x in C:
        ans += (C[x] * (C[x]-1)) // 2
    ans += C[0]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
res = 0
cnt = [0]*p
cnt[0]+=1
for i in range(n):
    res = (res+int(s[i])*pow(10, i, p))%p
    cnt[res]+=1
ans = 0
for c in cnt:
    if c<2:
        continue
    ans+=c*(c-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def solve2(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '02468':
            ans += i + 1
    return ans


def solve5(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans


def solve_other(s, p):
    remainders = defaultdict(lambda: 0)
    tmp = 0
    for c in s:
        c = int(c)
        tmp = (tmp * 10 + c) % p
        remainders[tmp] += 1
    ans = 0
    for r, cnt in remainders.items():
        if r == 0:
            ans += cnt * (cnt + 1) // 2
        else:
            ans += cnt * (cnt - 1) // 2
    return ans


n, p = list(map(int, input().split()))
s = input()
if p == 2:
    print(solve2(s))
elif p == 5:
    print(solve5(s))
else:
    print(solve_other(s, p))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, p = map(int, input().split())
def rev(x):
    return pow(x, p - 2, p)
s = list(map(int, input()))
rt = rev(10)
cur = 1
c = [0] * (n + 1)
ans = 0
t = defaultdict(int)
for i in range(n):
    t[c[i]] += 1
    c[i + 1] = (c[i] + cur * s[i]) % p
    cur = cur * rt % p
    ans += t[c[i + 1]]
print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int,input().split())
pr = [0 for _ in range(p)]
now = 0
s = input()
for i in range(n):
  now += int(s[i])
  now %= p
  pr[now] += 1
  now *= 10
  now %= p
#print(pr)
ans = 0
for x in pr:
  ans += x * (x-1)
ans //= 2
ans += pr[0]
print(ans)

Submission status: Wrong Answer

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

mod = 0
for s in S:
    s = int(s)
    mod = (mod * 10 + s) % P
    p_array[mod] += 1

ans = 0
for i, p in enumerate(p_array):
    if i == 0:
        ans += p
    ans += (p * (p-1) // 2)

print(int(ans))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p = LI()
    s = list(map(int, input()))[::-1]
    a = [0]
    for i in s:
        a.append((a[-1]+i)*10%p)
    ans = 0
    d = defaultdict(lambda : 0)
    for i in a:
        ans += d[i]
        d[i] += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

a = [0]
for c in S:
    c = int(c)
    a.append((a[-1]*10+c) % P)
from collections import Counter
ctr = Counter(a)

ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import Counter

rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m

def solve(N, P, S):
    A = map(int, S)
    powers = [0] * N
    pwr = 1
    for i in xrange(N-1, -1, -1):
        powers[i] = pwr
        pwr *= 10; pwr %= P

    #Xinv = modinv(10, P)
    count = Counter()
    count[0] += 1
    s = 0
    ans = 0
    for i in xrange(N-1, -1, -1):
        w = A[i] * powers[i] % P
        s += w; s %= P
        ans += count[s]
        count[s] += 1
        #print("!", ans)
    return ans


N, P = rrm()
print solve(N, P, rr())

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
C = [0] * P
C[0] = 1
X = []

a = 0
ans = 0
for s in S:
    a = (a * 10 + int(s)) % P
    ans += C[a]
    C[a] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, p = list(map(int, input().split()))
s = input()
r = {}
x = 0
ans = 0
for c in s:
	x = (x * 10 + int(c)) % p
	if x not in r:
		r[x] = 0
	ans += r[x]
	r[x] += 1
	if x == 0:
		ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
C = [0] * P
C[0] = 1
X = []

a = 0
ans = 0
for s in S[::-1]:
    a = (a * 10 + int(s)) % P
    ans += C[a]
    C[a] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
n,p = map(int,input().split())
s = input().rstrip()
ls = [0]
prev = 0
for i in range(n):
  x = int(s[i])
  y = (prev*10+x)%p
  ls.append(y)
  prev = y
c = Counter(ls)
ans = 0
for x in c.values():
  ans += x*(x-1)//2
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=[int(c) for c in input()]
ll=[0 for i in range(p)]
now=0
for i in l:
    now*=10
    now+=i
    now%=p
    ll[now]+=1
res=0
for i in range(p):
    res+=ll[i]*(ll[i]-1)//2
res+=ll[0]
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, p = na()
s = ns()

a = []
t = 1
for i in range(n-1, -1, -1):
    a.append((ord(s[i])-ord("0")) * t % p)
    t = t * 10 % p
cum = [0]
for v in a:
    cum.append((cum[-1] + v) % p)

dic = defaultdict(int)
ans = 0
for v in cum:
    ans += dic[v]
    dic[v] += 1
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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


prem = [0]*p
prem[0] = 1
curr_rem = 0
ans = 0
s = s[::-1]
for i,si in enumerate(s):
    sii = int(si)
    curr_rem = (sii*pow(10,i)+curr_rem)%p
    ans += prem[curr_rem]
    prem[curr_rem] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        num = 0
        point = 1
        for i in S_[::-1]:
            num += int(i) * point
            mod = int(num) % P
            mod_list[mod] += 1
            point *= 10
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        for i in range(N):
            num = S_[i:N]
            mod = int(num) % P
            mod_list[mod] += 1
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        for i in range(N):
            num = S_[i:N]
            mod = int(num) % P
            if mod == 0:
                ans += 1
            if mod_list[mod] >= 1:
                ans += mod_list[mod]
            mod_list[mod] += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        for i in range(N):
            num = S_[i:N]
            mod = int(num) % P
            if mod == 0:
                ans += 1
            mod_cnt = mod_list[mod]
            if mod_cnt >= 1:
                ans += mod_cnt
                mod_list[mod] += 1
                continue
            mod_list[mod] += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

    ans = 0
    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0

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

        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2

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



    print(ans)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n,p = map(int, input().split())
s = str(input())
m = 1
num = 0
for i in range(n):
    for h in range(m,n+1):
        w = s[i:h]
        if int(w)%p == 0:
            num += 1
    m += 1
print(num)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  i = 1
  for num in map(int, s):
    if num % p == 0:
      count += i
    i += 1
  print(count)
else:
  lst = [0 for _ in range(p)]
  i = n - 1
  w = int(s)
  q = w % p
  for num in map(int, s):
    lst[q] += 1
    q -= (num * 10 ** i) % p
    i -= 1
    if q < 0:
      q += p
  lst[0] += 1
  for ele in lst:
    count += ele * (ele - 1) // 2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  i = 1
  for num in map(int, s):
    if num % p == 0:
      count += i
    i += 1
  print(count)
else:
  lst = [0 for _ in range(p)]
  i = n - 1
  w = int(s)
  for num in map(int, s):
    q = w % p
    lst[q] += 1
    w -= num * 10 ** i
    i -= 1
  lst[0] += 1
  for ele in lst:
    count += ele * (ele - 1) // 2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  i = 1
  for num in map(int, s):
    if num % p == 0:
      count += i
    i += 1
  print(count)
else:
  lst = [0 for _ in range(p)]
  i = n - 1
  w = int(s)
  for num in map(int, s):
    q = w % p
    lst[q] += 1
    w -= num * 10 ** i
    i -= 1
  lst[0] += 1
  for ele in lst:
    count += ele * (ele - 1) // 2
  print(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(n):
    if int(s[i]) % p == 0:
      count += i + 1
  print(count)
else:
  lst = [0 for _ in range(p)]
  i = n - 1
  w = int(s)
  for num in map(int, s):
    q = w % p
    lst[q] += 1
    w -= num * 10 ** i
    i -= 1
  lst[0] += 1
  for i in range(p):
    v = lst[i]
    if v > 1:
      count += v * (v - 1) // 2
  print(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(n):
    if int(s[i]) % p == 0:
      count += i + 1
  print(count)
else:
  lst = [0] * p
  q = 0
  for i in range(n-1, -1, -1):
    if int(s[i]) != 0:
      num = int(s[i]) * 10 ** (n - i - 1)
    else:
      num = 0
    q += num % p
    if q >= p:
      q -= p
    lst[q] += 1
  lst[0] += 1
  for i in range(p):
    v = lst[i]
    if v > 1:
      count += v * (v - 1) // 2
  print(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(n):
    if int(s[i]) % p == 0:
      count += i + 1
  print(count)
else:
  lst = [0] * p
  q = 0
  for i in range(n-1, -1, -1):
    if int(s[i]) != 0:
      num = int(s[i]) * 10 ** (n - i - 1)
    else:
      num = 0
    q += num % p
    if q >= p:
      q -= p
    lst[q] += 1
  lst[0] += 1
  for i in range(p):
    value = lst[i]
    if value > 1:
      count += value * (value - 1) // 2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
lst = [0] * p
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:
  q = 0
  for i in range(n-1, -1, -1):
    num = int(s[i]) * 10 ** (n - i - 1)
    q += num % p
    q %= p
    lst[q] += 1
  lst[0] += 1
  for i in range(p):
    value = lst[i]
    if value > 1:
      count += value * (value - 1) // 2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
lst = [0] * p
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:
  num = int(s)
  for i in range(n):
    q = num % p
    lst[q] += 1
    num -= int(s[i]) * 10 ** (n - i - 1)
  lst[0] += 1
  for i in range(p):
    value = lst[i]
    count += value * (value - 1) // 2
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
lst = [0] * p
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:])
    q = num % p
    lst[q] += 1
  lst[0] += 1
  for i in range(p):
    value = lst[i]
    count += value * (value - 1) // 2
  print(count)

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:])
    q = num % p
    if q not in dic:
      dic[q] = 1
    else:
      dic[q] += 1
  if 0 not in dic:
    dic[0] = 1
  else:
    dic[0] += 1
  for i in range(p):
    value = dic.get(i, None)
    if value:
      count += value * (value - 1) // 2
  print(count)

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 i in range(p):
    value = dic.get(i, None)
    if value:
      count += value * (value - 1) // 2
  print(count)