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, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
enu = enumerate

sys.setrecursionlimit(10**7)
N, P = map(int, input().split())
S = input()

d = defaultdict(int)
for length in range(1, N+1):
    for index in range(N+1):
        if index + length > N:
            continue
        numstr = int(S[index:index+length])
        num = int(numstr)
        d[num] += 1

cnt = 0
for di in d.items():
    num, val = di[0], di[1]
    if num%P == 0:
        cnt += val

print(cnt)

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    tmp2 = 1
    for i in range(n):
        tmp += int(s2[i]) * tmp2
        tmp %= p
        tmp2 *= 10
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

    if P == 2:
        cnt = N * (N + 1) // 2
        for i, si in enumerate(S):
            if si & 1:
                cnt -= i + 1
        print(cnt)
        return

    cnt = 0
    for i in range(N):
        ans = 0
        for j in range(i, N):
            sj = S[j]
            ans = 10*ans + sj
            #print(ans, ans % P)
            if ans % P == 0:
                cnt += 1
    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def solve(inp):
    (N, P) = map(int, inp.readline().strip().split(' '))
    S = list(map(int, list(inp.readline().strip())))

    r = 0
    for i in range(len(S) - 1, -1, -1):
        n = 0
        d = 1
        for j in range(i, -1, -1):
            n += S[j] * d
            d *= 10
            if n % P == 0:
                r += 1

    return str(r)


def main():
    import sys
    result = solve(sys.stdin)
    if result is not None and result != '':
        print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)
def waru(n, p):
    return n % p == 0 

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

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

Submission status: Time Limit Exceeded

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

if p == 2:
    ans = 0
    for i in range(n):
        if s[i] %2 == 0:
            ans += i+1
    print(ans)
    exit()

if p == 5:
    ans = 0
    for i in range(n):
        if s[i] == 0 or s[i] == 5:
            ans += i+1
    print(ans)
    exit()

for i in range(n):
    s[i] *= pow(10, (n-1-i))
    s[i] %= p

ss = [0]

for i in range(n):
    ss.append(ss[-1]+s[i])
    ss[-1] %= p

ans = 0

for i in range(p):
    tmp = ss.count(i)
    ans += tmp*(tmp-1)//2

print(ans)

Submission status: Time Limit Exceeded

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

  ans = 0

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

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

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

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

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

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

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

x = 0
prevCounts = [0]*P

for s in S:
    s = int(s)
    nextCounts = [0]*P

    for i in range(P):
        nextCounts[(i*10 + s)%P] += prevCounts[i]

    nextCounts[s%P] += 1
    x += nextCounts[0]
    prevCounts = nextCounts


print(x)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
def main():
    n,p = tuple([int(t)for t in input().split()])

    s = input()
    counter =0
    for i in range(n):
        for j in range(i+1,n+1):
            subs = s[i:j]
            counter += 1 if int(subs)%p ==0 else 0

    print(counter)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

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

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    for i in range(n):
        tmp += int(s2[i]) * 10 ** i
        tmp %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
i=list(map(int, input().split()))
s=input()
n=i[0]
p=i[1]
l=[]
y=0
for j in range(0,n):
    for k in range (j,n):
        z=int(s[j:k+1])
        l.append(z)
for x in range (0,n*(n+1)//2):
    if l[x]%p==0:
        y=y+1
print (y)

Submission status: Time Limit Exceeded

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

cur = 0
cnt = 0
for a in range(N):
    cur = S[a]
    if cur%P == 0: cnt += 1
    for b in range(a+1,N):
        cur *= 10
        cur += S[b]
        if cur%P == 0: cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, P = [int(i) for i in input().split()]
S = input()
count = set()
c = 0
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        sub = S[i:j]
        if sub in count:
            c += 1
        elif int(sub)%P==0:
            count.add(sub)
            c += 1
print(c)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(0, len(s)):
    for j in range(i+1, len(s)+1):
        ans += (int(s[i:j]) % p == 0)
"""
        print(s[i:j],end = "\t")
        print(int(s[i:j]) % p)
print("============")
"""
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

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

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

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

for i in range(n):
  rem = int(s[i:]) % 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: Time Limit Exceeded

Solution code:
from itertools import accumulate

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2


N,P=map(int,input().split())
S=input()
if P!=2 and P!=5:
    data=[(int(S[i])*(10**(N-i-1)))%P for i in range(0,N)]
    ans=list(accumulate(data))
    ans=[ans[i]%P for i in range(0,N)]
    ans.append(0)
    print(equalfind(ans))
elif P==2:
    ans=0
    for i in range(0,N):
        if int(S[i])%2==0:
            ans+=i+1
    print(ans)
else:
    ans=0
    for i in range(0,N):
        if int(S[i])%5==0:
            ans+=i+1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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


memo = {}
ans = 0
for i in range(n):
    memo2 = {int(s[i]) % p: 1}
    for j in memo:
        if (j * 10 + int(s[i])) % p not in memo2:
            memo2[(j * 10 + int(s[i])) % p] = memo[j]
        else:
            memo2[(j * 10 + int(s[i])) % p] += memo[j]
    memo = copy.deepcopy(memo2)
    if 0 in memo:
        ans += memo[0]
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(left+1, N+1):
        if int(S[left:right]) % P == 0:
            count += 1
print(count)

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()
ans = 0

for i in range(n): 
    m = 0
    for j in range(i, n, 1): 
        m = m * 10 + (ord(s[j]) - ord('0')) 
        if (m % p == 0): 
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    K = {}
    r = 0
    for i in S:
        L = {}
        L[i % P] = 1
        for j, k in K.items():
            p = (j * 10 + i) % P
            L[p] = L.get(p, 0) + k
        r += L.get(0, 0)
        K = L
    return r
   

print(main())

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, P = [int(i) for i in input().split()]
S = input()
count = defaultdict(int)
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        # print(S[i:j])
        count[S[i:j]] += 1
c = 0
for i in count.keys():
    if int(i)%P==0:
        c += count[i]
print(c)

Submission status: Time Limit Exceeded

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
num = input().strip()
dp = [[0] * P for i in range(2)]
cur = True
ans = 0
for ele in num:
    last = ~cur
    cur_num = int(ele)
    for i in range(P):
        dp[cur][i] = 0

    for i in range(P):
        dp[cur][((i * 10) + cur_num) % P] += dp[last][i]
    dp[cur][cur_num % P] += 1
    ans += dp[cur][0]
    cur = ~cur
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
if p == 2:
	ans = 0
	for i in range(n):
		if int(s[i]) % 2 == 0:
			ans += i+1
	print(ans)
elif p == 5:
	ans = 0
	for i in range(n):
		if s[i] == "5" or s[i] == "0":
			ans += i+1
	print(ans)

else:
	mods = [0 for _ in range(p)]
	cur = 0
	mods[0] += 1
	t = s[::-1]
	for i in range(n):
		cur = (cur + int(t[i]) * (10 ** i)) % p
		mods[cur] += 1
	#print(mods)
	ans = 0
	for m in mods:
		ans += (m * (m-1)) // 2
	print(ans)

Submission status: Time Limit Exceeded

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

dp = [0] * P

ans = 0
for i, s in enumerate(map(int , S)):
    newDp = [0] * P
    newDp[s % P] += 1
    for p in range(P):
        newDp[(10 * p + s) % P] += dp[p]
    dp = newDp
    ans += dp[0]

print(ans)

Submission status: Time Limit Exceeded

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

def gen(s, n):
  for l in range(0, n):
    for r in range(l+1, n+1):
      yield int(s[l:r])

t = 0
for i in gen(S, N):
  if i % P == 0:
    t += 1
print(t)

Submission status: Time Limit Exceeded

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

dp = [[0] * P for _ in range(N + 1)]

for i, s in enumerate(map(int , S)):
    dp[i + 1][s % P] += 1
    for p in range(P):
        dp[i + 1][(10 * p + s) % P] += dp[i][p]

ans = 0
for d in dp:
    ans += d[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
string = ""
for i in range(N):
    string = S[i]
    # print(S[i])
    if int(string) % P == 0:
        ans += 1
    for j in range(i + 1, N):
        string += S[j]
        # print("\t"+str(S[j]))
        if int(string) % P == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
L = len(S)
ans = 0
for n in range(L-1):
    for m in range(n, L):
        if int(S[n:m+1]) % P == 0:
            ans += 1
if int(S[-1]) % P == 0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

table = [0] * p
r = 0
for i in range(len(s)):
    newtable = [0] * p
    newtable[s[i] % p] = 1
    for j in range(p):
        newtable[(j * 10 + s[i]) % p] += table[j]
    table = newtable
    r += table[0]
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,p = map(int,input().split())
s = list(input())
s = [int(x) for x in s]
d1 = defaultdict(int)

ans = 0
for x in s:
    d2 = defaultdict(int)
    for y in d1.keys():
        z = (10*y + x)%p
        d2[z] += d1[y]
    d2[x%p] += 1
    ans += d2[0]
    d1 = d2

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter

N, P = map(int, readline().split())
S = list(map(int, read().rstrip().decode()))

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))

Submission status: Time Limit Exceeded

Solution code:
N,P=[int(i) for i in input().split(" ")]
S=input()

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

print(retval)

Submission status: Accepted

Solution code:
# fin=open('in','r')
# input=lambda:fin.readline().strip()
n,p=map(int,input().split())
s=list(map(int,input()))
if p==2 or p==5:
  r=0
  for i in range(n):
    if s[i]%p==0:
      r+=i+1
  print(r)
else:
  c=0
  cnt=[0]*p
  cnt[0]+=1
  for k in range(len(s)-1,-1,-1):
      c=(c+s[k]*pow(10,len(s)-1-k,p))%p
      cnt[c]+=1
  print(sum(x*(x-1)//2 for x in cnt))

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,P=MI()
    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()
    
    
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    now=0
    dd[0]=1
    for i in range(N):
        now=now+(pow(10,i,P)*int(S[-1-i]))
        now%=P
        dd[now]+=1
        
    ans=0
    for k,v in dd.items():
        ans+=(v*(v-1))//2
        
    print(ans)
    

main()

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

def modinv(a,p):
    b,u,v = p,1,0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -=t*v
        u,v = v,u
    u %=p
    return u
n,p = ma()
s = input();s=s[::-1]

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

iv10 = modinv(10,p)
ls = [0]*n
for i in range(n):
    a = int(s[i])
    ls[i]=(ls[i-1]+a*pow(10,i,p))%p
co = collections.Counter(ls)
ans=co[0]
tmp=0
for i in range(0,n-1):
    a = int(s[i])
    co[ls[i]%p]-=1
    tmp = (tmp +a)*iv10%p
    r = tmp*pow(10,i+1,p)%p
    ans +=co[r]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num % p == 0:
            ans += i + 1
else:
    bfo, cnt = 0, [1] + [0] * (p - 1)
    for i, num in enumerate(s[::-1]):
        bfo = (bfo + pow(10, i, p) * num) % p
        ans += cnt[bfo]
        cnt[bfo] += 1
print(ans)

Submission status: Accepted

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,p)+curr_rem)%p
    ans += prem[curr_rem]
    prem[curr_rem] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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

ans=0

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

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0

if p in {2, 5}:
    lst = set(i for i in range(0, 10, p))
    for i, num in enumerate(s):
        if int(num) in lst:
            ans += i + 1
else:
    num = [0]
    for i in range(len(s)):
        tmp = num[-1] + pow(10, i, p) * int(s[-i - 1])
        num.append(tmp % p)
    mod = [0] * p
    for i in num:
        ans += mod[i]
        mod[i] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0

if p in {2, 5}:
    lst = set(i for i in range(0, 10, p))
    for i, num in enumerate(s):
        if int(num) in lst:
            ans += i + 1
else:
    num = [int(s[-1]) % p]
    for i in range(1, len(s)):
        tmp = num[-1] + pow(10, i, p) * int(s[-i - 1])
        num.append(tmp % p)
    mod = [1] + [0] * (p - 1)
    for i in num:
        ans += mod[i]
        mod[i] += 1
print(ans)

Submission status: Accepted

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

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N, P = MI()
S = ST()

ans = 0
if P == 2:
    for i, s in enumerate(S, 1):
        if int(s) % 2 == 0:
            ans += i
elif P == 5:
    for i, s in enumerate(S, 1):
        if int(s) % 5 == 0:
            ans += i
else:
    cnt = np.zeros(P)
    cnt[0] = 1
    res = 0
    tmp = 1
    for s in S[::-1]:
        res += int(s) * tmp
        res %= P
        cnt[res] += 1
        tmp *= 10
        tmp %= P

    for c in cnt[cnt >= 2]:
        ans += c * (c - 1) // 2

print(int(ans))

Submission status: Accepted

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
            point %= P
    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: Accepted

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
    print(ans)
else:
    lis = [0] * p
    cnt = 0
    kurai = 1
    for i in s[::-1]:
        cnt += i * kurai % p
        cnt %= p
        lis[cnt] += 1
        kurai *= 10
        kurai %= p
    ans = 0
    for i in lis:
        ans += i * (i - 1) // 2
    ans += lis[0]
    print(ans)

Submission status: Accepted

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

ans=0
if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    A=[0]
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        A.append(num)
        point *=10
        point %=p

    A=Counter(A)
    for i,j in A.items():
        if j>=2:ans +=j*(j-1)//2
print(ans)

Submission status: Accepted

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


INF=10**20
def solve(N,P,S,fact):
    ans = 0

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

 
    return ans

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 = list(next(tokens))  # type: str

    fact = [pow(10,i,P) for i in range(N)]

    S = list(map(int,S))
    S = np.array(S)
    print(solve(N, P, S,np.array(fact)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:],i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

if P in (2, 5):
    ans = sum(i for i, s in enumerate(S, 1) if not int(s) % P)
else:
    Acc = [0] * (N + 1)
    p10 = 1
    for i, s in enumerate(reversed(S)):
        Acc[N - i - 1] = (Acc[N - i] + p10 * int(s)) % P
        p10 = (p10 * 10) % P
    ans = sum(v * (v - 1) // 2 for v in Counter(Acc).values())
print(ans)

Submission status: Accepted

Solution code:
# これほんと納得行かない
N, P = map(int, input().split())
S = list(map(int, input()))
if P==2 or P==5:
    ans = 0
    for i, c in enumerate(S, 1):
        if c%P==0:
            ans += i
    print(ans)
    exit()
L = [0] * P
cum = 0
ans = 0
L[0] += 1
inv10 = pow(10, P-2, P)
base = 1
for c in S:
    cum = (cum + c * base) % P
    base = base * inv10 % P
    ans += L[cum]
    L[cum] += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
    allowed_digits = '24680' if p == 2 else '50'
    for i, c in enumerate(s, start=1):
        if c in allowed_digits:
            ans += i
else:
    count = Counter({0: 1})
    x, e = 0, 1
    for c in reversed(s):
        x = (x + (ord(c) - ord('0')) * e) % p
        e = e * 10 % p
        ans += count[x]
        count[x] += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
from collections import Counter
input = lambda: sys.stdin.readline().strip()
n, p = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
    allowed_digits = '24680' if p == 2 else '50'
    for i, c in enumerate(s, start=1):
        if c in allowed_digits:
            ans += i
else:
    def minv(x, p):
        return pow(x, p - 2, p)

    count = Counter({0: 1})
    x, delta = 0, 1
    for c in s:
        x = ((x * 10) + ord(c) - ord('0')) % p
        y = (x * minv(delta, p)) % p
        ans += count[y]
        count[y] += 1
        delta = (delta * 10) % p

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

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

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

cnt = [0] * P
base = 1
cur = 0
for c in S[::-1]:
    cur += (base * int(c)) % P
    cnt[cur % P] += 1
    base *= 10 
    base %= P
ans = 0
for i in cnt:
    if i == 0:
        continue
    ans += i * (i - 1) // 2
print(ans + cnt[0])

Submission status: Accepted

Solution code:
n, p = [int(i) for i in input().split()]
s = [int(i) for i in list(input())][::-1]
summ  = 0
ans = 0
cnt = [0]*p # あまりの部屋
cnt[0] = 1
for i in range(n):
    d = s[i]*pow(10, i ,p)
    summ = (summ + d) %p
    cnt[summ] +=1

if p in [2,5]: # 10の因数は別処理
    if p == 2:
        ok_list = [0,2,4,6,8]
    if p == 5:
        ok_list = [0,5]
    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n-i
else: # 他のは,あまりが同じものは差し引けばあまりが0になるのでpで割り切れる判定
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1)//2 # nC2の計算

print(ans)