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

counter=0
def power_func(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    elif b%2==1:
        return (a*power_func(a,b-1,p ))%p
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    temp=0
    for i in range(N):
        M = power_func(10,N-i,P)
        temp=(int(S[i])*M+temp)%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)

Submission status: Accepted

Solution code:

#####

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

#####

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


from sys import stdin
import sys

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



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

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

Submission status: Accepted

Solution code:
"""

問題文:

制約:

解読:
- 2, 5はO(n)で求められるとのこと
  - 最後の桁がpで割り切れるかどうかのみで判定可能なため
  - solve1で、cntをi + 1でカウントしている理由:
    - 対象となる部分文字列は連続した部分文字列
    - iをインクリメントしながらカウント
    - i番目の数字を含む部分文字列のみカウントすればよい -> (i + 1)個
"""
n, p = map(int, input().split())
s = list(map(int, list(input())))
u = [0 for _ in range(n + 1)]

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


def solve(u, s, p):
    if 2 == p or 5 == p:
        return solve1(s, p)
    else:
        return solve2(u, p)


def solve1(s, p):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i + 1
    return ans


def solve2(u, p):
    ans = 0
    cnt = [0 for _ in range(p)]
    for i in range(n + 1):
        cnt[u[i]] += 1
    for i in range(p):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans


print(solve(u, s, p))

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Solution code:
n,p=map(int,input().split())
S=input()
M=[0]*p
M[0]=1
ans=0

if p==2 or p==5: #最下位だけで決まるとき
    for i in range(n):
        s=int(S[i])
        if s%p==0:
            ans+=i+1
    
else: #それ以外は末尾に0をつけても割り切れるかが一致する
    cnt=10%p #10の累乗の剰余を記録しておく
    for i in range(n):
        s=int(S[n-1-i]) #右からi+1桁目を取り出す
        if i==0:
            r=s%p #剰余
        else:
            r=(cnt*s+r)%p #前の剰余にs*cntをたす
            cnt=cnt*10%p #更新
        if M[r]>=1: #同じ余りどうしで引き算すると割り切れる
            ans+=M[r]
        M[r]+=1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def toint(l, r):
    return int(''.join(map(str, S[l:r])))


def test():
    ans = 0
    for l, r in itertools.combinations_with_replacement(range(N), r=2):
        s = toint(l, r + 1)
        ans += s % P == 0
    print(ans)


def solve25():
    ret = 0
    for d in range(N):
        if S[d] % P == 0:
            ret += d + 1
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


N, P = list(map(int, sys.stdin.buffer.readline().split()))
S = list(map(int, list(sys.stdin.buffer.readline().decode().rstrip())))

# 10 mod P で割れない
if P in [2, 5]:
    ans = solve25()
    print(ans)
    exit()

# test()

powers = []
p = 1
for _ in range(N):
    powers.append(p)
    p = p * 10 % P
# int(S[1:1]), int(S[1:2]), int(S[1:3]), ...
s_additions = [0]
s = 0
for i in range(1, N):
    s = (s * 10 + S[i]) % P
    s_additions.append(s)
invs = mod_invs(max=P - 1, mod=P)


def to_index(i, p):
    # もともと x だったのが、i 番目で p になっているときの x を返す
    if i == 0:
        return p % P
    return (p - s_additions[i]) * invs[powers[i]] % P


mod_counts = [0] * P
ans = 0
for i, c in enumerate(S):
    mod_counts[to_index(i, c)] += 1
    ans += mod_counts[to_index(i, 0)]
print(ans)

Submission status: Accepted

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

u = [ 0 for i in range(n+1)]

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

# print(u, d)

def solve(u, s):
    if p == 2 or p == 5:
        return solve1(s)
    else:
        return solve2(u)


def solve1(s):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    return ans

def solve2(u):
    ans = 0
    cnt = [0 for i in range(p)]
    for i in range(n+1):
        cnt[u[i]] += 1
    for i in range(p):
        q = cnt[i]
        ans += (q * (q-1)) // 2
    return ans

print(solve(u, s))

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
    for l, s in enumerate(S, 1):
        if int(s) % P == 0: ans += l
else:
    counter = [0] * P
    counter[0] = 1
    prev = 0
    temp = 1
    for i, s in reversed(list(enumerate(S))):
        num = (int(s) * temp + prev) % P
        ans += counter[num]
        counter[num] += 1
        prev = num
        temp = (temp * 10) % P
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N, P = map(int, input().split())
S = list(map(int,list(input())))
U = [0 for i in range(N+1)]

d = 1
for i in range(N):
    U[N-(i+1)] = (U[N-i] + S[N-1-i] * d) % P
    d = 10 * d % P
    
def solve(U,S):
    if P == 2 or P == 5:
        return solve1(S)
    else:
        return solve2(U)
    
def solve1(S):
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    return ans

def solve2(U):
    ans = 0
    cnt = [0 for i in range(P)]
    for i in range(N+1):
        cnt[U[i]] += 1
    for i in range(P):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans

print(solve(U,S))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P
        m += prev
        m %= P
        cummod[m] += 1
        d *= 10
        d %= P
        prev = m

    #cummod[0] += 1

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n - 1) // 2

    ans += cummod[0]

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P
        m += prev
        m %= P
        cummod[m] += 1
        d *= 10
        d %= P
        prev = m

    cummod[0] += 1

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n - 1) // 2

    #ans += cummod[0]

print(ans)

Submission status: Accepted

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    lis=[1]
    for i in range(n-1):
        lis.append((lis[i]*10)%p)
    lis.reverse()
    for i in range(n):
        lis[i]=(int(s[i])*lis[i])%p
    unum=[1]
    for i in range(p-1):
        unum.append(0)
    num=0
    for i in range(n):
        num=(num+lis[n-i-1])%p
        unum[num]+=1
    for i in range(p):
        unumi=unum[i]
        count+=(unumi*(unumi-1))*0.5
print(round(count))

Submission status: Accepted

Solution code:
#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

def main():
    n,p=map(int,input().split())
    s=list(map(int,list(input())))
    
    if p==2 or p==5:
        cnt=0
        for i in range(n):
            if s[i]%p==0:
                cnt+=i+1
        print(cnt)

    else:
        pmod=[0]*p
        cummod=0
        ten=1
        for i in range(n):
            cummod+=s[-i-1]*ten
            cummod%=p
            pmod[cummod]+=1
            ten*=10
            ten%=p
        
        ans=pmod[0]
        for i in range(p):
            k=pmod[i]
            if k >=2 :
                ans+=k*(k-1)//2
        print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,p = inm()
acc = [0]*(n+1)
a = [0]*(n+1)
ss = ins()
s = ss[::-1]
if p in [2,5]:
    x = 0
    for i in range(n):
        if int(s[i])%p==0:
            x += n-i
    print(x)
    exit()

q = 1
for i in range(n):
    x = int(s[i])
    r = q*x
    acc[i+1] = (acc[i]+r)%p
    #ddprint(f"i {i} x {x} r {r} q {q} ai {acc[i+1]}")
    q = (q*10)%p
ddprint(acc)
h = [0]*p
for i in range(n+1):
    h[acc[i]] += 1
ddprint(h)
sm = 0
for i in range(p):
    x = h[i]
    sm = (sm+x*(x-1)//2)
print(sm)

Submission status: Accepted

Solution code:
def solve2(s):
    ans = 0
    for i, c in enumerate(s): #見る数字を右に広げていく
        if c in '02468':
            ans += i + 1 # 見ている数字のの一番右の桁が偶数ならその頭に乗っている数字の数だけ
                        # 答えに追加する
                        # 例 2254とし2→偶数、22→偶数（さらに先頭の2をどけても偶数）
                        # →225（奇数）→2254（偶数、上の3つをそれぞれどけても偶数）
    return ans


def solve5(s): # p==2のときと同じ原理
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans


def solve_other(s, p):
    ans = 0
    last_mod=0
    mods = [0]*p
    mods[0] = 1 #初期値として何も選んでない状態を1個加えとく
    digit = 1
    for i in range(n-1,-1,-1): # 一番右のけたから見る
        last_mod = (last_mod + int(s[i])*digit)%p # 最新のmodに新しく見ている桁*(10**x)を足してmod計算
        ans += mods[last_mod] # modリストに直前までのの値を答えに追加
        mods[last_mod] += 1 # modリスト更新
        digit=digit*10%p # 桁上げ
    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:
from collections import defaultdict
n,p = map(int,input().split())
s = input()

sur1 = [int(s[0]) % p]
sur2 = [int(s[-1]) % p]
sur10 = [1 % p]
for i in range(n-1):
    sur1 += [(sur1[i] * 10 + int(s[i+1])) % p]
    sur10 += [(sur10[i] * 10) % p]
    sur2 += [(sur2[i] + sur10[i+1] * int(s[-i-2])) % p]

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

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

d = defaultdict(int)
for x in sur2:
    d[x] += 1

for k,v in d.items():
    if k == 0:
        ans += v * (v+1) // 2
    else:
        ans += v * (v-1) // 2
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    readline=stdin.readline
    N,P=map(int,readline().split())
    S=readline().strip()
    r=[0]*(N+1)

    if P!=2 and P!=5:
        now=1
        for i in range(N):
            a=(int(S[N-i-1])*now)%P
            r[i+1]=(a+r[i])%P
            now*=10
            now%=P
        
        d=dict()
        for n in range(P):
            d[str(n)]=0
        d["0"]=1

        ans=0
        for i in range(1,N+1):
            ans+=d[str(r[i])]
            d[str(r[i])]+=1
            
        print(ans)

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

        print(ans)

if __name__=="__main__":
    main()

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(len(s)):
    if int(s[i]) % p == 0:
      ans += i + 1
    
  print(ans)
  sys.exit(0)
  

last_mod = 0
keta_mod = 1
mod_array = [0] * p
mod_array[0] = 1



for i in reversed(range(len(s))):
  tmp = int(s[i]) * keta_mod
  last_mod = (last_mod + tmp) % p
  keta_mod = (keta_mod * 10) % p
  mod_array[last_mod] += 1
  
ans = 0
for v in mod_array:
  ans += v * (v-1) // 2
  
print(ans)

Submission status: Accepted

Solution code:
#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

Submission status: Accepted

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

ans = 0

if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
else:
    count = [0] * P
    count[0] = 1
    u = 0
    for i, s in enumerate(reversed(S)):
        u = (int(s) * pow(10, i, P) + u) % P
        ans += count[u]
        count[u] += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
  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:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    r = 0
    for i in range(N):
      # r = int(S[N-1-i:])%P
      # とするとTLEになってしまう。
      r = (r + int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()

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:
def main():
  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:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    r = 0
    for i in range(N):
      r = (r+int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//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 in (2, 5):
  print(sum(i+1 for i in range(n) if s[i]%p == 0))
  exit(0) 
ans = g = 0
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g = (g + s[i]*t)%p
    ans += d[g]
    d[g] += 1
    t = (t*10)%p
print(ans)

Submission status: Accepted

Solution code:
import math
import collections

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

ans = 0
juu = 1
S = S[::-1]
amari = 0
amaris = [0] * (P) #あまりの配列
if P == 2 or P == 5:
    for i,c in enumerate(S):
        n = int(c)
        if n % P == 0:
            ans += N - i
else:


    for c in S:
        i = int(c)
        amari += (i * juu)
        amari %= P
        amaris[amari] += 1
        juu *= 10
        juu %= P


    amaris[0] += 1
    for temp in amaris:
        ans += temp * (temp - 1) //2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import copy
import queue
def LI(): return [int(x) for x in input().split()]
n,p = LI()
s = input()
cnt = 0
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
       if int(s[i]) % p == 0:
           cnt += (i+1)
else:
    num = 0
    p10 = 1
    p_cnt = [1] + [0 for _ in range(p-1)]
    for i in range(n-1,-1,-1):
        num = (num + p10 * int(s[i])) % p
        p_cnt[num] += 1
        p10 = (p10 * 10) % p
    for i in range(p):
        cnt += p_cnt[i] * (p_cnt[i]-1) // 2
print (cnt)

Submission status: Accepted

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

d = [0]*(N+1)
# d[N-1] = 1

if 10%P == 0:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
else:
    ## 10の何乗か
    ten = 1
    ## 一桁目から、Pの余りを累積和
    for i in range(N-1,-1,-1):
        a = int(S[i]) * ten % P
        d[i] = (d[i+1]+a)%P
        ten *= 10
        ten %= P

    ## dの値を累積カウントする
    counter = [0]*P
#     print(d)
    for j in range(N, -1, -1):
        ans += counter[d[j]]
#         print(ans)
        counter[d[j]] += 1

    print(ans)

Submission status: Accepted

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


def mod_pow(a, n, mod):
  res = 1
  while  n > 0:
    if n & 1:
      res = (res * a ) % mod
    a = a * a  % mod
    n = n >> 1
  return res

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
    number = (number + int(S[i-1])*mod_pow(10, N - i, P)) % P
    Pa[number] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)

Submission status: Accepted

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    counter = [0] * p
    counter[0] = 1
    cur = 0
    p10 = 1
    ans = 0
    for x in s[::-1]:
        cur = (cur + int(x) * p10) % p
        ans += counter[cur]
        counter[cur] += 1
        p10 *= 10
        p10 %= p
    print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict

def main():
    N, P = map(int, input().split())
    S = list(map(int, list(input())))
    ans = 0
    if P == 2:
        for i in range(N-1,-1,-1):
            if S[i] % 2 == 0:
                ans += i + 1
        print(ans)
        exit()
    if P == 5:
        for i in range(N-1,-1,-1):
            if S[i] % 5 == 0:
                ans += i + 1
        print(ans)
        exit()
    
    ten = 1
    d = defaultdict(int)
    C = [0] * (N + 1)
    for i in range(N-1,-1,-1):
        tmp = (S[i] * ten) % P
        idx = N - 1 - i
        C[idx + 1] = (C[idx] + tmp) % P
        ten *= 10
        ten %= P

    for c in C:
        d[c] += 1

    for i, j in d.items():
        ans += j * (j - 1) // 2

    print(ans)    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

res = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            res += i + 1
else:
    mp = [0]*P
    mp[0] = 1
    cur = 0
    p10 = 1
    for c in S[::-1]:
        cur = (cur + int(c)*p10) % P
        res += mp[cur]
        mp[cur] += 1
        p10 *= 10
        p10 %= P

print(res)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N,P = LI()
S = list(map(int,list(str(input()))))

ans = 0
if P == 2:
    for i in range(N):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    for i in range(N):
        if S[i]%5 == 0:
            ans += i+1
else:
    M = [0]*(N+1)
    now = 0
    for i in range(N):
        now += pow(10,i,P)*S[N-1-i]
        now %= P
        M[N-1-i] = now
    d = defaultdict(list)
    for i in range(N+1):
        d[M[i]].append(i)
    for i in range(N):
        p = bisect_left(d[M[i+1]],i+1)
        ans += p

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


def solve():
    N, P = map(int, input().split())
    S = input()
    if (10 % P == 0):
        ans = 0
        for i in range(N):
            if int(S[N - i - 1]) % P == 0:
                ans += N - i
        return ans
    ten = 1
    cur = 0
    val = [0] * P
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * ten) % P
        ten *= 10
        ten %= P  # ある数XがPで割れるならXを10倍したものもPで割れるはずなので.
        val[cur] += 1
    ans = 0
    for p in range(P):
        ans += val[p] * (val[p] - 1) // 2
    return ans


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline()[:-1]

def solve():
    N, P = map(int, input().split())
    S = input()
    if 10%P == 0:
        ans = 0
        for i in range(N):
            if int(S[N-i-1]) % P == 0:
                ans += N - i
        
        return ans
    
    ten = 1
    cur = 0
    val = [0] * P
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N-i-1])*ten) % P
        ten *= 10
        ten %= P
        val[cur] += 1
    ans = 0
    for p in range(P):
        ans += val[p] * (val[p] - 1) // 2
    
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


def solve():
    N, P = map(int, input().split())
    S = input()
    if (10 % P == 0):
        ans = 0
        for i in range(N):
            if int(S[N - i - 1]) % P == 0:
                ans += N - i
        return ans
    ten = 1
    cur = 0
    val = [0] * P
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * ten) % P
        ten *= 10
        ten %= P
        val[cur] += 1
    ans = 0
    for p in range(P):
        ans += val[p] * (val[p] - 1) // 2
    return ans


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) for i in d) // 2
print(r)

Submission status: Accepted

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * i - i for i in d) // 2
print(r)

Submission status: Accepted

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Accepted

Solution code:
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  s, y = 0, 1
  for x in reversed(a):
    s = (s + x * y) % p
    d[s] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Accepted

Solution code:
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(reversed(a), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Accepted

Solution code:
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    d=i*pow(10,n,P)
    tmp =(tmp+d)%P
    cnt[tmp] += 1
if P in [2,5]:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S):
        if i in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)