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: Accepted

Solution code:
n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])%p
t=10
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)

Submission status: Accepted

Solution code:
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    if P == 2 or P == 5:
        r = 0
        for i, s in enumerate(S):
            if s % P == 0:
                r += (i + 1)
        return r

    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = P
    for i in range(2, P):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    H = [0] * N
    h = 0
    for i, s in enumerate(S):
        h = (h * 10 + s) % P
        H[i] = h
    K = [0] * P
    K[0] = 1
    shift = 1
    r = 0
    for i, h in enumerate(H):
        t = (h * inverse[shift]) % P
        r += K[t]
        K[(h * inverse[shift]) % P] += 1
        shift = (shift * 10) % P

    return r
   

print(main())

Submission status: Accepted

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

n,p = map(int,input().split())
s = list(input())
for i in range(n):
    s[i] = int(s[i])


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

else:
    d = 1
    q = [0]
    for i in range(n-1,-1,-1):
        q.append((q[-1]+s[i]*d)%p)
        d = d*10%p
    q.sort()
    res = 0
    i = 0
    while i < n+1:
        k = bisect.bisect_right(q,q[i])
        c = k-i
        res += c*(c-1)//2
        i = k
    print(res)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,p = nm()
s = list(map(int, list(ns())))
ans = 0
if p == 2:
  for i in range(n):
    if s[i]%2 == 0:
      ans += i+1
  print(ans); exit(0)
if p == 5:
  for i in range(n):
    if s[i]%5 == 0:
      ans += i+1
  print(ans); exit(0)
   
g = [0]*(n+1)
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g[i] = (g[i+1] + s[i]*t)%p
    ans += d[g[i]]
    d[g[i]] += 1
    t = (t*10)%p
print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

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


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
l = list(reversed(list(S)))
each = [0]*N
ten = 1
for i in range(N):
    each[i] = int(l[i])*ten%P
    ten = ten*10%P
Sum = [0]*N
num = 0
for i in range(N):
    num = (num + each[i])%P
    Sum[i] = num
Sum.sort()
fac = Sum[0]
ans = 0
cnt = 0
for i in range(N):
    if Sum[i] == 0:
        ans += 1
    if Sum[i] == fac:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        fac = Sum[i]
ans += cnt*(cnt-1)//2
if P != 5 and P != 2:
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(l[i])%P == 0:
            ans += N-i
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

import numpy as np

n, p = map(int, input().split())
d = deque(input())

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    k = int(d.popleft())
    if k % p == 0:
      ans += i + 1
else:
  sub = [0 for i in range(n)]
  wk = 0
  for i in range(n):
    k = int(d.pop())
    wk = (wk + k * pow(10, i, p)) % p
    sub[i] = wk
  ans = 0
  dic = {}
  for i in range(n):
    if sub[i] == 0:
      ans += 1
    if sub[i] in dic.keys():
      ans += dic[sub[i]]
      dic[sub[i]] = dic[sub[i]] + 1
    else:
      dic[sub[i]] = 1

print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
S=input()[::-1]
if p==2 or p==5:
    ans=0
    for i in range(n):
        if int(S[i])%p==0:
            ans+=n-i
    print(ans)
    exit()
mod=[0]*(n+1)
mod_l=[0]*p
mod_10=[1]*n
for i in range(n-1):
    mod_10[i+1]=mod_10[i]*10%p
for i in range(n):
    mod[i+1]=(mod[i]+int(S[i])*mod_10[i])%p
for i in range(n+1):
    mod_l[mod[i]]+=1
ans=0
for i in range(p):
    ans+=mod_l[i]*(mod_l[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

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

if P == 2 or P == 5:
    s_can = [1 if i % P == 0 else 0 for i in S]
    # s_cant = [0 if i == 1 else 0 for i in s_can]
    # s_acc = list(accumulate(s_can[::-1]))[::-1]
    answer = 0
    for idx, i in enumerate(s_can[::-1]):
        if i:
            answer += N - idx
    print(answer)
else:
    s = []
    t = 1
    for i in S[::-1]:
        r = i % P
        s.append(r * t % P)
        t = t * 10 % P

    s = list(accumulate([0] + s))
    s = [i % P for i in s]
    c = Counter(s)
    answer = 0
    for i in c.values():
        answer += i * (i - 1) // 2

    print(answer)

Submission status: Accepted

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

import sys
if p==2 or p==5:
    count=0
    for i in range(n):
        if int(s[i])%p==0:
            count+=i+1
    print(count)

    sys.exit()
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
inv=modinv(10,p)
pmod=[0]*p
pmod[0]=0
buf=0
count=0
for i in range(n):
    buf*=10
    buf+=int(s[i])
    buf%=p
    idx=buf*pow(inv,i,p)
    idx%=p
    count+=pmod[idx]
    pmod[idx]+=1
#print(pmod)
print(count+pmod[0])

Submission status: Accepted

Solution code:
N ,P= map(int,input().split())
S = input()
ten = [0] * len(S)
for i in range(len(S)):
    if i == 0:
        ten[i] = 1
    else:
        ten[i] = (ten[i-1] * 10) %P
if P != 2 and P != 5:
    mod_dic ={}
    mod_dic[0] = 1
    mod = 0
    for i in range(len(S)):
        mod +=  int(S[N-1-i]) * ten[i]
        mod = mod%P
        if mod not in mod_dic:
            mod_dic[mod] = 1
        else:
            mod_dic[mod] += 1
        ans = 0
    a = list(mod_dic.values())
    for i in range(len(a)):
            ans += a[i] * (a[i]-1) //2
    print(ans)
elif P == 2:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%2 == 0:
            ans += N-i
    print(ans)
else:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%5 == 0:
            ans += N-i
    print(ans)

Submission status: Accepted

Solution code:
n,p = (int(num) for num in input().split())
s = input()
s = s[::-1]

if p != 2 and p != 5:
    dec = [1] * n
    for i in range(1,n):
        dec[i] = (dec[i - 1] * 10) % p
    s_mod = [0] * n
    for i in range(n):
        s_mod[i] = (int(s[i]) * dec[i]) % p

    #print(dec)
    #print(s_mod)

    cumsum = [0] * (n + 1)
    cnt = [1] + [0] * (p - 1)
    for i in range(n):
        cumsum[i + 1] = (cumsum[i] +  s_mod[i]) % p
        cnt[cumsum[i + 1]] += 1
    #print(cumsum)
    #print(cnt)

    ans = 0
    for i in range(p):
        ans += (cnt[i] * (cnt[i] - 1)) // 2
    print(ans)
elif p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += n - i
    print(ans)
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % 5 == 0:
            ans += n - i
    print(ans)

Submission status: Accepted

Solution code:
import sys, collections
range = xrange
input = raw_input

n, p = [int(x) for x in input().split()]
A = [ord(x) - 48 for x in input()]


if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if A[i]%p == 0:
            ans += i + 1
    print ans
    sys.exit()


DP = [0]*p
ans = 0
POW = 1
ind0 = 0
for a in reversed(A):
    DP[ind0] += 1
    #DP = [DP[(a * POW + i) % p] for i in range(p)]
    ind0 = (a * POW + ind0) % p
    ans += DP[ind0]
    POW = POW * 10 % p
print ans

Submission status: Accepted

Solution code:
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    po = [1]*N
    for i in range(N-1):
        po[i+1] = (po[i]*10)%P
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * po[i]
        l[i] = a%P
        b += l[i]
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mod = p

if mod < 10:
    d = {0:0}
    ans = 0
    for i in t:
        nxt = defaultdict(int)
        for key,value in d.items():
            nxt[(key*10 + i)%mod] += value
        nxt[i%mod] += 1
        ans += nxt[0]
        d = nxt
    print(ans)
else:
    cnt = [0]*mod
    f = 1
    ans = 0
    cur = 0
    for i in reversed(range(n)):
        cur += f*t[i]
        cur %= mod
        ans += cnt[cur]
        cnt[cur] += 1
        if cur == 0:
            ans += 1
        f *= 10
        f %= mod
    print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = list(reversed(list(map(int, input()))))
if p == 2:
    ans = 0
    s = list(reversed(s))
    for i in range(n):
        if s[i] % 2 == 0:
            ans += i + 1
    print(ans)
    exit()
if p == 5:
    ans = 0
    s = list(reversed(s))
    for i in range(n):
        if s[i] % 5 == 0:
            ans += i + 1
    print(ans)
    exit()
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: Accepted

Solution code:
n,p = map(int,input().split())
a = list(map(int,list(input())))
ans = 0
if p == 2:
  for i in range(n):
    if a[i]%2==0:
      ans += i+1
elif p == 5:
  for i in range(n):
    if a[i]==5 or a[i]==0:
      ans += i+1
else:
  b = 0
  c = [0 for i in range(p)]
  c[0] = 1
  for i in range(n):
    b = (b+pow(10,n-i,p)*a[i])%p
    c[b] += 1
  c = list(map(lambda x:x*(x-1)//2,c))
  ans = sum(c)
print(ans)

Submission status: Accepted

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

S = input()

total = 0
if P == 2 or P == 5:
	for i, s in enumerate(S):
		if int(s) % P == 0:
			total += i + 1
else:
	counts = [0] * P
	counts[0] = 1
	h = 0
	
	d = 1
	for s in reversed(S):
		m = int(s) * d % P
		h = (h + m) % P
		total += counts[h]
		counts[h] += 1
		d = (d * 10) % P

#print(counts)

print(total)

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, s in enumerate(S):
        if s%P==0: ans+=i+1
    print(ans)
    exit()

R = [None]*N
k = 1
for i in range(N-1, -1, -1):
    R[i] = S[i]*k%P
    k = k*10%P

ans = 0
X = []
x = 0
for r in R:
    x  = (x+r)%P
    X.append(x)

D = [0]*P
D[0] = 1
for x in X:
    ans += D[x]
    D[x]+=1

print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
s=input()
ans=0
if(p==2 or p==5):
    kensa=["0","2","4","6","8"]
    if(p==5):
        kensa=["0","5"]
    for i in range(n):
        if(s[i] in kensa):
            ans+=i+1
else:
    amari=0
    ju=1

    cnt=[0]*p
    cnt[0]=1

    for i in range(n):
        amari+=int(s[n-i-1])*ju
        amari%=p
        ju=(ju*10)%p
        cnt[amari]+=1
    for c in cnt:
        if(c==0 or c==1):
            continue
        ans+=c*(c-1)//2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    if P==5:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%5==0:
                ans += N-i
        print(ans)
        return
    elif P==2:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%2==0:
                ans += N-i
        print(ans)
        return

    for i in range(N):
        s = int(S[N-1-i])
        cur += s*pow(10,i,P)
        A[i+1] = cur%P
    D = [0]*P
    for a in A:
        D[a] += 1
    ans = 0
    #print(A)
    for d in D:
        ans += d*(d-1)//2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

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

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

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

n = len(s)
l = [0 for i in xrange(n + 1)]

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

p10 = 1
for i in xrange(n - 1, 0, -1):
    p10 *= 10
    if p10 >= p: p10 %= p
    l[i] = p10 * (ord(s[i - 1]) - 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 + 1):
    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)

print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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

if p == 2 or p == 5:
    ans = 0
    for i, item in enumerate(s):
        if int(item) % p == 0:
            ans += (i + 1)
else:
    mods = [0]
    s = s[::-1]
    mod = 0
    for i, ch in enumerate(s):
        mod = (mod + int(ch) * pow(10, i, p))  % p
        mods.append(mod)
    
    cnt = [0] * p
    for item in mods:
        cnt[item] += 1
    ans = 0
    for item in cnt:
        ans += item * (item - 1) // 2
print(ans)

Submission status: Accepted

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())))

if 10%P==0:
    ans= 0
    for i,s in enumerate(S):
        if s%P == 0:
            ans += i+1
    print(ans)
else:
    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: Accepted

Solution code:
from collections import defaultdict
n,p = map(int,input().split())
s = list(input())
s = [int(x) for x in s][::-1]
if p != 2 and p != 5:
    ans = 0
    data = [0 for _ in range(p)]
    now = 1
    data[0] = 1
    a = 0
    for i in range(n):
        a += now*s[i]
        a %=p
        data[a]+=1
        now *= 10
        now %= p
    for x in data:
        ans += x*(x-1)//2
    print(ans)
if p == 2:
    ans = 0
    for i,x in enumerate(s[::-1]):
        if x%2 == 0:
            ans += i+1
    print(ans)
if p == 5:
    ans = 0
    for i,x in enumerate(s[::-1]):
        if x%5 == 0:
            ans += i+1
    print(ans)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
rem=[0]*n
cnt=[0]*p
s=input()[::-1]
if p==5:
    s=s[::-1]
    ans=0
    for i in range(n):
        if int(s[i])%5==0:
            ans+=i+1
    print(ans)
    exit()
if p==2:
    s=s[::-1]
    ans=0
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
    print(ans)
    exit()
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: Accepted

Solution code:
from collections import Counter
n, p = map(int, input().split())
s = list(map(int, input()))
ans = 0
if p == 2:
    for i, c in enumerate(s):
        if c % 2 == 0:
            ans += i + 1
elif p == 5:
    for i, c in enumerate(s):
        if c % 5 == 0:
            ans += i + 1
else:
    l = [0] * (n + 1)
    for i, c in enumerate(s):
        l[i + 1] = l[i] + pow(10, n - i - 1, p) * c
        l[i + 1] %= p
    for v in Counter(l).values():
        ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

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

if P != 2 and P != 5:
    p_array = [0] * P
    mod = 0
    amari = 1
    for i, s in enumerate(S[::-1]):
        s = int(s)
        mod = (mod + s * amari) % P
        amari = amari * 10 % 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: Accepted

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

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

if P==2:
    L=[int(s)%2 for s in S[::-1]]

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

elif P==5:
    L=[int(s)%5 for s in S[::-1]]

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

else:   
    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: Accepted

Solution code:
from itertools import accumulate,chain
from collections import defaultdict


def solve(N,P,S):
    S = list(map(int,S))

    if P == 2:
        cnt = 0
        for i,n in enumerate(S):
            if n%2 == 0:
                cnt += i+1
        return cnt
    elif P == 5:
        cnt = 0
        for i,n in enumerate(S):
            if n%5 == 0:
                cnt += i+1
        return cnt


    n = 1
    T = [None]*N
    for i in reversed(range(N)):
        T[i] = (n*S[i])%P
        n *= 10
        n %= P
    T = tuple(chain((0,),accumulate(T, lambda a,b: (a+b)%P)))



    cnt = 0
    c = defaultdict(int)
    for t in T:
        cnt += c[t]
        c[t] += 1
    return cnt

if __name__ == '__main__':

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

Submission status: Accepted

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

Solution code:
from collections import Counter
N, P = map(int, input().split())
if P not in [2,5]:
  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])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)

Submission status: Accepted

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()

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%P
    x = (x*x)%P
    n = n >> 1 #ビットシフト
  return ans%P

if P!=2 and P!=5:
    data=[(int(S[i])*(pow(10,N-1-i)))%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: Accepted

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)
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % 5 == 0:
            ans += (i + 1)
else:
    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: Accepted

Solution code:
from collections import Counter
n, p = map(int, input().split( ))
s = input()
#n,p = 10000,5
#s = "7"*10000
#p=2,5は例外
#例外でなければ累積和
if p==2:
    ans = 0
    for i in range(n):
        if int(s[i])%2==0:
            ans += i+1
    print(ans)
    exit()
if p==5:
    ans=0###
    for i in range(n):
        if int(s[i])%5==0:
            ans += i+1
    print(ans)
    exit()


accm = [0]
s = s[::-1]
#print(s)
sm = 0
beki_p = 1
for i in range(n):
    sm += int(s[i])*beki_p
    sm %=p
    accm.append(sm)
    beki_p *=10
    beki_p%=p

aC = Counter(accm)
ans = 0
for k in aC:
    ans += aC[k]*(aC[k]-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
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
    print(ans)
    sys.exit()

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: Accepted

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()))
    if p in [2,5]:
        ans = 0
        for i in range(n):
            si = s[i]
            if si%p == 0:
                ans += i+1
        print(ans)
        return
    a = [0]
    k = pow(10,p-2,p)
    K = k
    for i in range(n):
        si = s[i]
        a.append((a[-1]+si*K)%p)
        K *= k
        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: Accepted

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

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

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

    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: Accepted

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):
    reminders = defaultdict(lambda: 0)
    tmp = 0
    mul = 1
    for c in s[::-1]:
        c = int(c)
        tmp = (tmp + c * mul) % p
        mul = mul * 10 % p
        reminders[tmp] += 1
    reminders[0] += 1
    ans = 0
    for r, cnt in reminders.items():
        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: Accepted

Solution code:
n,p = map(int,input().split())
pr = [0 for _ in range(p)]
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()
ten = [1]
for i in range(n-1):
  ten.append(ten[-1]*10%p)
ten.reverse()
#print(ten)
pr[0] = 1
now = 0
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: Accepted

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()

s = s[::-1]
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
for c in counter:
    ans += c * (c-1)//2
print(ans)

Submission status: Accepted

Solution code:
def calc(S, P):
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += i + 1
        return ans
    else:
        C = [0] * P
        C[0] = 1
        a = 0
        for i, s in enumerate(S[::-1]):
            a = (a + int(s) * pow(10, i, P)) % P
            ans += C[a]
            C[a] += 1
        return ans

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