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:
#E
N,P = map(int,input().split())
S = list(str(input()))

zcount = S.count("0")

U = []
for i in range(N):
    u = int(S[N-i-1])
    U.append(u)
    
npow = 1
T = [0]
now = 0
for i in range(N):
    now += U[i]*npow
    now %= P
    T.append(now)
    npow*=10
    npow%=P
    
pmod = [0]*P
for t in T:
    pmod[t]+=1
    
ans1 = 0
for p in pmod:
    ans1 += (p*(p-1))//2
    
if P != 2 and P != 5:
    print(ans1)
else:
    ans2 = 0
    for i in range(N):
        u = U[i]
        if u%P == 0:
            ans2+=N-i
    print(ans2)

Submission status: Accepted

Solution code:
from collections import *
n, p = map(int, input().split())
s = list(map(int, input()))
if 10%p==0:
    r = 0
    for i in range(n):
        if s[i]%p==0:
            r += i+1
    print(r)
    exit()
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
    v += int(i)*k
    v %= p
    r += c[v]
    c[v] += 1
    k *= 10
    k %= p
print(r)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[N-1 - i]) % P == 0:
            ans += N-i
    print(ans)
else:
    A = [0] * (N+1)
    for i in range(N):
        A[i+1] = (A[i] + int(S[N-1 - i]) * pow(10, i, P)) % P

    c = collections.Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v-1) // 2
    
    print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
        p %= P
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
def input():return sys.stdin.readline().strip()

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

    ans = 0
    if P in [2, 5]:
        for i, c in enumerate(S[::-1]):
            if int(c) % P == 0:
                ans += N-i
    else:
        d = defaultdict(int)
        d[0] = 1
        num = 0
        ten = 1
        for c in S[::-1]:
            num += int(c) * ten
            num %= P
            d[num] += 1
            ten *= 10
            ten %= P

        ans = sum([d[i]*(d[i]-1)//2 for i in range(P)])

    print(ans)

        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        A = [0] * N
        tenpow = 1
        for i in range(N):
            A[i] = (S[i]*tenpow) % P
            tenpow *= 10
            tenpow %= P
        D = [0] * (N+1)
        for i in range(N):
            D[i+1] = (D[i] + A[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

ans = 0

if 10 % P == 0:
    for r in range(len(A)):
        if int(A[r]) % P == 0:
            ans += r + 1
    print(ans)
    sys.exit()


A = "0" + A[::-1]

S = [0] * len(A)
cnt = [0] * P
cnt[0] = 1

for i in range(len(A) - 1):
    S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, P)) % P
    cnt[S[i + 1] % P] += 1
# print(S, cnt)

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

Submission status: Accepted

Solution code:
def main():
    N, P = (int(i) for i in input().split())
    L = [int(s) for s in input()][::-1]
    ans = 0
    if P == 2 or P == 5:
        for i, e in enumerate(L):
            if e % P == 0:
                ans += N-i
    else:
        A = [0]*N
        d = 1
        for i, e in enumerate(L):
            A[i] = (e*d) % P
            d *= 10
            d %= P
        S = [0]*(N+1)
        for i in range(N):
            S[i+1] = S[i] + A[i]
            S[i+1] %= P
        from collections import Counter
        c = Counter(S)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

import bisect#2分探索
#bisect_left(l,x), bisect(l,x)
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = int(input())
N, P = map(int, input().split())
S=input()
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入
if P!=2 and P!=5:
    pc=[0]*P
    pc[0]=1
    count=0
    ans=0
    p10=1
    for i in range(1,N+1):
        count+=int(S[N-i])*p10
        count%=P
        ans+=pc[count]
        pc[count]+=1
        p10*=10
        p10%=P

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

import bisect#2分探索
#bisect_left(l,x), bisect(l,x)
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = int(input())
N, P = map(int, input().split())
S=input()
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入
if P!=2 and P!=5:
    pc=[0]*P
    pc[0]=1
    count=0
    ans=0
    for i in range(1,N+1):
        count+=int(S[N-i])*pow(10,(i-1),P)
        count%=P
        ans+=pc[count]
        pc[count]+=1

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

Submission status: Accepted

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

if p==2:
    ans=0
    for i,j in enumerate(s):
        if j%2==0:
            ans+=(n-i)
    print(ans)
    exit()
if p==5:
    ans=0
    for i,j in enumerate(s):
        if j%5==0:
            ans+=(n-i)
    print(ans)
    exit()

c=[0]*p
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%p]+=1
    t=(t*10)%p
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
#import queue
from copy import copy, deepcopy
from operator import itemgetter

import bisect#2分探索
#bisect_left(l,x), bisect(l,x)
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#q=heapq.heapify(l),heappush(q,a),heappop(q)

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = int(input())
N, P = map(int, input().split())
S=input()
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入
if P!=2 and P!=5:
    l=[0]*(N+1)
    count=0
    for i in range(1,N+1):
        count+=int(S[N-i])*pow(10,(i-1),P)
        l[i]=count%P

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

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
if 10 % P == 0:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += r + 1
    print(ans)
    exit()

d = [0] * (N + 1)
ten = 1
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

cnt = [0] * P
ans = 0
for i in range(N, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def main():
    n, p = map(int, input().split())
    s = list(input())
    if 10 % p == 0:
        ans = 0
        for i in range(n):
            if (ord(s[i])-ord('0')) % p == 0:
                ans += i+1
        print(ans)
        return

    d = [0] * (n+1)
    ten = 1
    for i in reversed(range(n)):
        a = (ord(s[i])-ord('0')) * ten % p
        d[i] = (d[i+1]+a) % p
        ten *= 10
        ten %= p

    cnt = [0] * p
    ans = 0
    for i in reversed(range(n+1)):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
s=input()
b=1
d=0
l=[0]*p
l[0]=1
ans=0
for i,c in enumerate(s[::-1]):
  if p==2 or p==5:
    if int(c)%p==0:
      ans+=n-i
  else:
    d+=int(c)*b
    d%=p
    l[d]+=1
    b*=10
    b%=p
if p!=2 and p!=5:
  for i in l:
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,mod = map(int,input().split())
S = list(map(int,input()))
if mod == 2:
  for i in range(n):
    if S[i] % 2 == 0:
      ans += i+1
elif mod == 5:
  for i in range(n):
    if S[i] % 5 == 0:
      ans += i + 1
else:
  tenpow = 1
  for i in range(n-1,-1,-1):
    S[i] = S[i] * tenpow % mod
    tenpow = tenpow * 10 % mod
  acum = [0]*(n+1)
  for i in range(n):
    acum[i+1] = (acum[i]+S[i]) % mod
  C = collections.Counter(acum)
  for key,item in C.items():
    ans += (item-1) * item //2


print(ans)

Submission status: Accepted

Solution code:
def main():
    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)
        return
    if p == 5:
        ans = 0
        for i in range(n):
            if int(s[i])%5 == 0:
                ans += i+1
        print(ans)
        return
    dp = [0 for _ in range(p)]
    dp[0] += 1
    x = 0
    
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,p))%p
        dp[x] += 1
    ans = 0
    for i in range(p):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = input()
r = set()
last = 0
d = {0: 0}
total = 0
rem = 0
if p == 2:
    for i in range(0, len(s)):
        if int(s[i]) % 2 == 0:
            total += i + 1
    print(total)
elif p == 5:
    for i in range(0, len(s)):
        if int(s[i]) % 5 == 0:
            total += i + 1
    print(total)



else:
    power = 1
    for i in range(len(s) - 1, -1, -1):  # handling of 0's as n and rem
        n = int(s[i]) * power + rem
        power *= 10
        power = power % p
        rem = n % p
        if rem in d.keys():
            d[rem] += 1
        else:
            d[rem] = 1
        total += d[rem] - 1
    print(total + d[0])

Submission status: Accepted

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

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if S[i]%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    ans = 0
    for i in range(l-1, -1, -1):
        temp += S[i]*pow(10, l-i-1, P)
        temp %= P
        ans += data[temp]
        data[temp] += 1
    ans += data[0]

print(ans)

Submission status: Accepted

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

def solve():
    total = 0

    if 10%p == 0:
        for i in range(n):
            if s[i] % p == 0: total += i + 1
        return total

    cnt = [0]*p
    r = 0
    ten = 1
    for i in range(n-1, 0-1, -1):
        cnt[r] += 1
        r = (r + s[i]*ten) % p
        total += cnt[r]
        ten = ten * 10 % p
    return total

print(solve())

Submission status: Accepted

Solution code:
'''ika tako　　ABC164Dの類題
基本は、1桁目、2桁目と下から10進数の数字として見て、
素数ｐで割った余りを考え、余りが同じである数字のスタートとエンドを
選ぶ組み合わせの数が答。
但し、10進数で考えているので、ｐが2と5のケースは別扱い。
末尾が2、5の倍数なら2の倍数。先頭の数字を0番目として、
i番目に2、5の倍数が出てきたら、
そこを右端とする部分文字列は i+1  個作れる。
'''
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:
from collections import Counter
N, P = map(int, input().split())
S = input()

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

else:
    X = [0]
    for i, s in enumerate(S[::-1]):
        X.append((X[-1] + pow(10, i, P) * int(s)) % P)

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

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:
    s = s[::-1]
    cnt = {0: 1}
    now = 0
    d = 1
    for i in range(n):
        now = (now + int(s[i]) * d) % p
        res += cnt.get(now, 0)
        d = (d * 10) % p
        cnt[now] = cnt.get(now, 0) + 1

print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split());s=input();l=[0]*m;a,t,p=0,0,1
if 10%m:
  for i in s[::-1]:l[t%m]+=1;t+=int(i)*p;a+=l[t%m];p=p*10%m
else:a=sum(i+1 for i in range(n) if int(s[i])%m<1)
print(a)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
l=[0]*m
a,t,p=0,0,1
if 10%m:
  for i in s[::-1]: l[t%m]+=1; t+=int(i)*p; a+=l[t%m]; p=p*10%m
else:
  a=sum(i+1 for i in range(n) if int(s[i])%m<1)
print(a)

Submission status: Accepted

Solution code:
'''
0から9までの数字から成る長さNの文字列Sの部分文字列の内、
十進数表記の整数とみなした時、素数Pで割り切れるものの個数を求めよ。
部分文字列は先頭が0であっても良く、文字列の位置で区別する。

terms:
    1<=n<=2*10**5
    2<=p<=10**4

input:
    4 3
    3543

output:
    6
'''

from collections import defaultdict
import sys
input = sys.stdin.readline
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** -7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
n, p = inpl()
s = input()[:-1]
arr = [int(s[i]) for i in range(n)]
ans = 0
if p == 2 or p == 5:
    '''
    10を割り切ると桁の話が使えないので場合分け
    1の位が割り切れればそれだけ
    '''
    for i in range(n):
        if arr[i] % p == 0:
            ans += i + 1
    print(ans)
else:
    '''
    Pが10の約数である2,5だと以下の仮定が成り立たないので使えない
    ・ある数XがPで割り切れるならそれを10倍したものもPで割り切れる

    f(i)=Sの下i桁をPで割った時の余り
    として、f(i)=f(j)になる組を考える。
    するとiからj桁目までの値はPで割り切れる(i%p-j%p≡(i-j)%p)
    pow(x,y,z)=x^y%z
    '''
    dic = defaultdict(int)
    # dic = { 余り: 個数}
    now = 0
    dic[0]=1 # 余り0ならまず条件一致。それ以外だったら同じあまりが出た時点で条件一致
    for i in range(n-1,-1,-1): #下i桁をpで割った余り
        now += arr[i] * pow(10, n - 1 - i, p)
        now %= p
        ans+=dic[now]
        dic[now] += 1
    
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, P = map(int, input().split())
S = input()[:-1]

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

cnt = defaultdict(int)
cnt[0] = 1
now = 0
ans = 0

for i in range(N-1, -1, -1):
    now = (int(S[i])*pow(10, N-1-i, P)+now)%P
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Submission status: Accepted

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

if P == 2 or P == 5:
  for i, s in enumerate(S):
    if int(s) % P == 0:
      ans += i + 1
else:
  l = [0] * P 
  l[0] = 1
  Sum = 0
  digits = 1
  
  for c in S[::-1]:
    Sum += int(c) * digits % P
    Sum %= P
    l[Sum] += 1
    digits = digits * 10 % P
  
  for i in range(len(l)):
    ans += l[i] * (l[i] - 1) // 2
  
print(ans)

Submission status: Accepted

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

if P == 2 or P == 5:
    for i, t in enumerate(S[::-1]):
        temp = int(t)
        if temp % P == 0:

            ans += N - i
    print(ans)
    exit()

for i, t in enumerate(S[::-1]):
    now = (now + int(t) * pow(10, i, P)) % P
    ans += hyou[now]
    hyou[now] += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, P = map(int, input().split())
    *s, = map(int, input())

    if P in {2, 5}:
        ans = 0
        for i, x in enumerate(reversed(s), start=0):
            if x % P == 0:
                ans += N - i
        print(ans)
        return

    ans = 0
    total = 0
    coef = 1
    ctr = [0] * P
    ctr[0] = 1
    for x in reversed(s):
        total = (total + x * coef) % P
        coef = coef * 10 % P
        ans += ctr[total]
        ctr[total] += 1
    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, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = (digit * 10) % p
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n,p = map(int,input().split())
s = input()
n = len(s)
mod = [0] * (n+1)
ten = [0] * n

a = 1
for i in range(n):
    ten[i] = a
    a = a * 10 % p

ans = 0
if p != 2 and p != 5:
    rui = 0
    for i in range(n):
        rui = (int(s[n-1-i]) * ten[i] + rui) % p
        mod[n-1-i] = rui

    b = Counter(mod)
    c = list(b.values())
    c.sort(reverse = True)

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

print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
if p in (2, 5):
  c = 0
  for i, x in enumerate(map(int, input()[::-1])):
    if x % p == 0:
      c += n-i
  print(c)
else:
  c = [0] * p
  y = 0
  t = 1
  for x in map(int, input()[::-1]):
    y = (y + t*x) % p
    c[y] += 1
    t = (10 * t) % p
  print(sum(i * (i-1) // 2 for i in c) + c[0])

Submission status: Accepted

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

ans = 0

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

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

num = 1
l = [0]
for i in range(n-1, -1, -1):
    l.append((num * s[i] + l[-1]) % p)
    num *= 10
    num %= p

from collections import Counter

dic = Counter(l)
for i in dic.values():
    ans += i * (i - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,P = LMIIS()
    S = input()[::-1]
    R = [0]*P
    R[0] = 1
    b = 1
    r = 0


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

    for c in S:
        r += b * int(c)
        r %= P
        R[r] += 1
        b *= 10
        b %= P
    ans = 0

    for r in R:
        ans += r*(r-1)//2
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        inv%=k
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N, P = map(int, input().split())
S = input()
ans = 0
if P == 2:
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i+1
elif P == 5:
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i+1
else:
    cnt = [0 for _ in range(P)]
    cnt[0] = 1
    bai = 1
    v = 0
    for i in range(N)[::-1]:
        v = (v + int(S[i]) * bai) % P
        bai *= 10
        bai %= P
        cnt[v] += 1
    for i in range(P):
        ans += ((cnt[i] - 1 ) * cnt[i]) // 2
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mods = [0] * P
        mods[0] = 1
        current = 0
        x = 1
        for s in S:
            current = (current + x * int(s)) % P
            ans += mods[current % P]
            mods[current % P] += 1
            x = x * 10 % P
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()
S=S[::-1]

ans=0
if P in (2,5):
    len_S=len(S)
    for i,x in enumerate(S):
        x=int(x)
        if x%P==0:
            ans+=(len_S-i)
    print ans
else:
    L=[0] 
    val=0
    for i,x in enumerate(S):
        x=int(x)
        val+=pow(10,i,P)*x
        L.append(val%P)

    C=defaultdict(lambda: 0)
    for x in L:
        ans+=C[x]
        C[x]+=1
    print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()
S=S[::-1]

ans=0
if P in (2,5):
    len_S=len(S)
    for i,x in enumerate(S):
        x=int(x)
        if x%P==0:
            ans+=(len_S-i)
    print ans
else:
    L=[0] 
    val=0
    for i,x in enumerate(S):
        x=int(x)
        val+=pow(10,i,P)*x
        L.append(val%P)

    C=defaultdict(lambda: 0)    #mod2019の値の出現個数を記録
    for x in L:
        ans+=C[x]   #自分とmod2019の結果が同じ値となる出現個数をansに足す
        C[x]+=1     #自分のmod2019の値を出現個数に+1カウント
    print ans

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
S=input()[::-1]
ans=0
if p==2:
    for i,s in enumerate(S):
        if int(s)%2==0:
            ans+=(n-i)
    print(ans)
    exit()

if p==5:
    for i,s in enumerate(S):
        if int(s)==0 or int(s)==5:
            ans+=(n-i)
    print(ans)
    exit()


sd=0
d=1
count=[0]*(p+1)
count[0]+=1
for s in S:
    sd+=int(s)*d
    d*=10
    sd%=p
    d%=p
    count[sd]+=1

for cnt in count:
    ans+=cnt*(cnt-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, P = map(int, input().split())
S = input().strip()[::-1]

if P in [2, 5]:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += N - r
    print(ans)
    exit()

cum = [0] * (N + 1)
for i in range(N):
    now = int(S[i]) * pow(10, i, P)
    cum[i + 1] = (cum[i] + now) % P

cnt = defaultdict(int)
for _cum in cum:
    cnt[_cum] += 1

ans = 0
for k, v in cnt.items():
    ans += v * (v - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input().strip()[::-1]

if P in [2, 5]:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += N - r
    print(ans)
    exit()

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

cnt = [0] * P
ans = 0
for i in range(N + 1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
if P == 2:
    for i, d in enumerate(S):
        if d in "02468":
            ans += i + 1
elif P == 5:
    for i, d in enumerate(S):
        if d in "05":
            ans += i + 1
else:
    x = 1
    curr = 0
    mods = [0] * P
    mods[0] = 1
    for d in reversed(S):
        curr = (curr + x * int(d)) % P
        ans += mods[curr % P]
        mods[curr % P] += 1
        x = x * 10 % P
print(ans)

Submission status: Accepted

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