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:
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    s = 0
    for i in range(len(S)-1, -1, -1):
        s = (s + int(S[i])*pow(10, N-1-i, P)) % P
        if s == 0:
            p[s] += 1
            ans += p[s]
        else:
            ans += p[s]
            p[s] += 1

    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    s = 0
    for i in range(len(S)-1, -1, -1):
        s = (s + int(S[i])*pow(10, N-1-i, P)) % P
        m = s % P
        if m == 0:
            p[m] += 1
            ans += p[m]
        else:
            ans += p[m]
            p[m] += 1

    print(ans)

Submission status: Accepted

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

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

    print(ans)
    exit()

ans = 0
tmp = 0
rem = [0] * p
rem[0] = 1
for i in range(n):
    tmp = (tmp + int(s[-1 * (i+1)]) * pow(10, i, p)) % p
    ans += rem[tmp]
    rem[tmp] += 1

print(ans)

Submission status: Accepted

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

if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            count += i + 1
else:
    mod_count = [0] * P
    mod_count[0] = 1
    revS = S[::-1]

    modp = 0
    mod10 = 1

    for i in range(N):
        mod10 = (mod10 * 10) % P
        modp = (modp + mod10 * revS[i]) % P

        mod_count[modp] += 1

    for i in range(P):
        count += mod_count[i] * (mod_count[i] - 1) // 2
print(count)

Submission status: Accepted

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

else:
    tmp1=1
    tmp2=0
    for i in range(n-1,-1,-1):
        tmp2=(tmp1*int(s[i])+tmp2)%p
        x[tmp2]+=1
        tmp1=(tmp1*10)%p

    ans+=x[0]
    for i in range(p):
        ans+=x[i]*(x[i]-1)//2
    print(ans)

Submission status: Accepted

Solution code:
##mod M における　aの逆元を求めてくれる
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
#すなわちax==1(mod m)なる自然数xを返してくれる関数 動作時間:logM
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n,p=map(int,input().split())
ans=0
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    modlist[0]=0
    modlist[1]=int(s[0])%p  
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    K=pow(10,p-2,p)
    invlist=[0 for i in range(n+1)]
    invlist[0]=1
    invlist[1]=K
    for i in range(2,n+1):
        invlist[i]=(invlist[i-1]*K)%p
    uselist=[0 for i in range(n+1)]
    for i in range(n+1):
        uselist[i]=(modlist[i]*invlist[i])%p
    ANS=dict(collections.Counter(uselist))
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
else:
    q=0
    for i in range(n):
        q+=1
        if int(s[i])%p==0:
            ans+=q
    print(ans)

Submission status: Accepted

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

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sum = 0
  for i in range(n):
    sum = (sum+s[n-i-1]*pow(10,i,p))%p
    cnt[sum] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)

Submission status: Accepted

Solution code:

N,P=map(int,input().split())
S=input()
amari=[0 for _ in range(P)]
amari[0]=1
cnt=0
num=0
if (P==5)or(P==2):
    for i in range(N-1,-1,-1):
        #print(S[i])
        if int(S[i])%P==0:
            cnt=cnt+i+1
else:
    for i in range(N-1,-1,-1):
        #print(S[i],pow(10,N-i-1))
        num=num+int(S[i])*pow(10,N-1-i,P)
        #print(num)
        index=num%P
        amari[index]=amari[index]+1
    #print(amari)
    for i in range(P):
        cnt=cnt+(max(0,amari[i])*max(0,amari[i]-1))/2
        
print(int(cnt))

Submission status: Accepted

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

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = c * w + k
        w *= 10
        while k >= p:
            k -= p
        while w >= p:
            w -= p
        cnt[k] += 1

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

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    reslst[0]+=1
    tmp=1
    now=0
    for i in [int(x) for x in s[::-1]]:
        now+=i*tmp
        now%=p
        reslst[now]+=1
        tmp=(tmp*10)%p
    
    for i in range(p):
        cnt+=reslst[i]*(reslst[i]-1)//2

print(cnt)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
num = input().strip()
ans = 0
if P == 2:
    for idx, nu in enumerate(num):
        if nu in '24680':
            ans += idx + 1
elif P == 5:
    for idx, nu in enumerate(num):
        if nu in '50':
            ans += idx + 1
else:
    nnum = [0] * N
    base = 1
    for i in range(N-1, -1, -1):
        nnum[i] = (int(num[i]) * base) % P
        base = (base * 10) % P
    for i in range(1, N):
        nnum[i] = (nnum[i] + nnum[i-1]) % P
    dp = [0] * P
    for i in range(N):
        if nnum[i] == 0:
            ans += 1 + dp[nnum[i]]
        else:
            ans += dp[nnum[i]]
        dp[nnum[i]] += 1
print(ans)

Submission status: Accepted

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

mod = p
l = 100

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

T = [1]
for i in range(n-1):
    T.append((T[-1]*10) % p)

P = [0] * p
P[0] = 1

ans = 0
v = 0
S = [int(s[i]) for i in range(n-1,-1,-1)]

import math

if p==2 or p==5:
    for i in range(n):
        ans += (int(s[i]) % p == 0) * (i+1)
elif math.log10(p) in [1,2,3,4]:
    print("Wrong Answer")
else:
    for i in range(n):
        v = (v + T[i]*S[i]) % p
        ans += P[v]
        P[v] += 1
        # print(P)

print(ans)

Submission status: Accepted

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


def solve(N: int, P: int, S: str):
    if P == 2 or P ==5:
        answer = 0
        for i in range(N):
            if int(S[i])%P == 0:
                answer += i+1
        print(answer)
        return

    amari = [0]*N
    amari[N-1] = int(S[N-1])%P
    keta = 1
    for i in range(N-2,-1,-1):
        num = pow(10,keta,P)*int(S[i])
        amari[i]=(amari[i+1]+num)%P
        keta += 1
    from collections import Counter
    counter = Counter(amari)
    answer = 0
    for _,value in counter.items():
        answer += (value*(value-1))//2
    answer += amari.count(0)
    print(answer)  
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, P, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    if p==2 or p==5:
        ans=0
        for i,c in enumerate(s):
            if int(c)%p==0:ans+=i+1
        print(ans)
        exit()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
    print(ans)

main()

Submission status: Accepted

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

answer=0
if P==2 or P==5:
  for i in range(N):
    si=int(S[i])
    if si%P==0:
      answer+=i+1
else:
  mod_table=[0]*P
  mod_table[0]=1
  revS=S[::-1]
  
  modp=0
  mod10=1
  for i in range(N):
    mod10=(mod10*10)%P
    #modp=(10*modp+int(revS[i]))%P
    modp=(modp+mod10*int(revS[i]))%P
    mod_table[modp]+=1
    
  #print(mod_table)
  for i in range(P):
    answer+=mod_table[i]*(mod_table[i]-1)//2
  
print(answer)

Submission status: Accepted

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

import sys
from itertools import accumulate
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, P = MAP()
A = list(map(int, input()))

if P == 2 or P == 5:
    ans = 0
    for i, a in enumerate(A):
        if a % P == 0:
            ans += i + 1
    print(ans)
    exit()

acc = [0] * N
cur = A[-1] % P
acc[-1] = cur
k = 1
for i in range(N-2, -1, -1):
    cur += pow(10, k, P) * A[i]
    cur %= P
    acc[i] = cur
    k += 1
acc = acc + [0]

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

Submission status: Accepted

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

N, P = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1
else:
    U = [0] * (N+1)
    count = [0] * P
    count[0] = 1
    factor = 10
    for i in range(N)[::-1]:
        U[i] = (S[i] * factor + U[i+1]) % P
        factor = factor * 10 % P
        ans += count[U[i]]
        count[U[i]] += 1
print(ans)

Submission status: Accepted

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

ans=0
if 10%P==0:
    for r in range(N):
        if int(S[r])%P==0:
            ans+=r+1
else:
    d=[0 for _ in range(N+1)] # Pで割った余りの累積和
    ten=1 # 10の何乗か
    for i in range(N-1, -1, -1): # 右から見ていく
        a=int(S[i])*ten%P
        d[i]=(d[i+1]+a)%P
        ten=(ten*10)%P
    cnt=[0 for _ in range(P)]
    for i in range(N, -1, -1):
        ans+=cnt[d[i]]
        cnt[d[i]]+=1
print(ans)

Submission status: Accepted

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

mod = p
l = 100

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

T = [1]
for i in range(n-1):
    T.append((T[-1]*10) % p)

P = [0] * p
P[0] = 1

ans = 0
v = 0
S = [int(s[i]) for i in range(n-1,-1,-1)]

if p==2 or p==5:
    for i in range(n):
        ans += (int(s[i]) % p == 0) * (i+1)
else:
    for i in range(n):
        v = (v + T[i]*S[i]) % p
        ans += P[v]
        P[v] += 1
        # print(P)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    ruijo=1
    for i in range(n):
        ruijo%=p
        s+=int(S[-(i+1)])*(ruijo)
        a=s%p
        kouho[a]+=1
        ruijo*=10
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
def main():
    N,P=map(int, input().split())
    S=input()
    B=[(ord(c)-ord("0"))%P for c in S]
    ans=0
    if P==2 or P==5:
        for i,b in enumerate(B,1):
            if b==0:
                ans+=i
    else:
        D={0:1}
        x=0
        y=1
        for b in B[::-1]:
            x=(x+(b*y))%P
            D.setdefault(x,0)
            ans+=D[x]
            D[x]+=1
            y=(y*10)%P
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    sss = 0
    for i, ss in enumerate(s[::-1]):
        sss = (sss + pow(10, i, p) * int(ss)) % p
        m[sss] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

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

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: 
            res += i+1
    print(res)
    quit()
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i,p)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)

Submission status: Accepted

Solution code:

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

S = input()


if P not in [2,5]:

    dic = {}
    dic[0] = 1
    now = 0
    ans = 0

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

    print (ans)

elif P == 2:

    ans = 0
    for i in range(N):

        if int(S[i]) % 2 == 0:
            ans += i+1

    print (ans)

else:

    ans = 0

    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())
S = input()
ans = 0
C = [0] * P
C[0] = 1
a = 0
if P in (2, 5):
    print(sum([i+1 for i, s in enumerate(S) if int(s) % P == 0]))
    exit()
    
for i, s in enumerate(S[::-1]):
    a = (a + int(s) * pow(10, i, P)) % P
    ans += C[a]
    C[a] += 1
print(ans)

Submission status: Accepted

Solution code:
import collections

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
    print(ans)
else:
    S = S[::-1]
    a, temp = [int(S[0]) % P], 1
    for i in range(1, N):
        temp *= 10
        temp %= P
        a.append((a[i-1] + (int(S[i]) % P * temp) % P) % P)

    c = collections.Counter(a)
    if 0 in c:
        ans += c[0]
        ans += c[0] * (c[0] - 1) // 2
        del c[0]
    for x in c.keys():
        ans += c[x] * (c[x]-1) // 2 
    print(ans)

Submission status: Accepted

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

ans = 0

d = {i:0 for i in range(p)}
d[0] = 1

ap = 1
if p not in [2, 5]:
    pre = 0
    for si in s[::-1]:
        si = int(si)
        a = (si * ap + pre) % p
        ans += d[a]
        d[a] += 1
        pre = a
        ap = (ap * 10) % p
else:
    for i, si in enumerate(s):
        if int(si) % p == 0:
            ans += i+1
print(ans)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    N,P = map(int,input().split())
    s = input()
    l = len(s)
    ans = 0
    if 10%P == 0:
        for i,st in enumerate(s[::-1]):
            num = int(st)
            if num%P == 0:
                ans += l-i
    else:
        rest = [0]
        t = 1
        for st in s[::-1]:
            num = int(st)%P
            rest.append(num*t%P)
            t = t*10%P
            
        for i in range(l):
            rest[i+1] += rest[i]

        for i in range(l):
            rest[i+1] %= P
            
        c = Counter(rest)
        c = list(c.values())
        for num in c:
            ans += num*(num-1)//2
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

else:
    data = [0] * P
    s = int(S)
    x = 1 ##10**iをPで割った数
    y = 0 ##S[i:N]をPで割った数
    for i in range(N):
        y += int(S[N-i-1]) * x
        y %= P
        data[y] += 1
        x *= 10
        x %= P
    #print(data)
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
if p == 2 or p == 5:
    for i in range(n - 1, -1, -1):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()


k = 1
for i in range(n - 1, -1, -1):
    d = int(s[i])
    rem = (k * d + rem) % p
    k = k * 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)

Submission status: Accepted

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

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

if mod == 2 or mod == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s)%mod==0:
            ans += i+1
else:
    dp = [0]
    t = 1
    for s in reversed(S):
        dp.append((dp[-1]+int(s)*t)%mod)
        t = t*10%mod

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in tuple(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    d=defaultdict(int)
    tmp=0
    digit=1
    ans=0
    for i,s in enumerate(reversed(S)):
        tmp+=s*digit
        digit*=10
        digit%=p
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
C = [0] * P
C[0] = 1
a = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
    print(ans)
else:
    for i, s in enumerate(S[::-1]):
        a = (a + int(s) * pow(10, i, P)) % P
        ans += C[a]
        C[a] += 1
    print(ans)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      count += i + 1
  print(count)
else:
  mod = [0] * p
  mod[0] = 1
  tmp = 0
  ten = 1
  for i in s[::-1]:
    ten = ten * 10 % p
    tmp = (tmp + int(i) * ten) % p
    mod[tmp] += 1
  for m in mod:
    count += m * (m - 1) // 2
  print(count)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, P = map(int, input().split())
S = list(map(int, list(input())[: -1]))
rcs = [0] * (N + 1)
for i in range(N, 0, -1): rcs[i - 1] = (rcs[i] + S[i - 1] * pow(10, N - i, P)) % P
#print(rcs)
d = dd(list)
for i in range(N + 1):d[rcs[i]].append(i)
res = 0
if P == 2 or (P == 5):
  for i in range(N - 1, -1, -1):
    res += (S[i] % P == 0) * (i + 1)
  print(res)
  exit(0)
table = [0] * P
for i in range(N, -1, -1):
  x = rcs[i]
  res += table[x]
  table[x] += 1
print(res)

Submission status: Accepted

Solution code:
NN = 2020202
MOD = 10**9+7
INF = float("inf")

n, p = map(int, input().split())
S = input()
pl = len(str(p))

if p == 2 or p == 5:
    count = 0
    for i in range(len(S)):
        if int(S[i])%p == 0:
            count += i+1
            # print(int(S[i]), count)

    print(count)

else:
    d = [0] * p
    d[0] = 1
    val = 0
    dec = 1

    for i in range(len(S)-1, -1, -1):
        val = (int(S[i])*dec+val)%p
        dec = (dec*10)%p
        d[val] += 1

    # print(d)
    ans = 0
    for e in d:
        ans += (e*(e-1))//2
    print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
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])==0 or int(s[i])==5:
            ans+=i+1
else:
    count=[0]*p
    x=0
    y=1
    count[0]=1
    for i in range(n-1,-1,-1):
        x=x+y*int(s[i])
        x=x%p
        count[x]+=1
        y=(y*10)%p
    ans=0
    for i in count:
        ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

if p == 2 or p == 5:
    d = {2: "02468", 5: "05"}
    ans = 0
    for i, e in enumerate(s, 1):
        if e in d[p]:
            ans += i

    print(ans)

else:
    li = [0]
    power = 1
    for e in s[::-1]:
        power *= 10
        power %= p
        li.append((li[-1] + int(e) * power) % p)

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

    print(ans)

Submission status: Accepted

Solution code:

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

def main():
    N,P=MI()
    s=input()
    ans=0
    if P==2 or P==5:
        for i in range(N):
            t=int(s[i])
            if t%P==0:
                ans+=i+1
            
    else:
        ans=0
        t=0
        mod=[0]*P
        mod[0]=1
        for i in range(N):
            t=t+int(s[N-i-1])*pow(10,i,P)
            t=t%P
            mod[t]+=1
            if mod[t]>=2:
                ans+=mod[t]-1
                

            

    print(ans)   
        
    
            
    
        
    

main()

Submission status: Accepted

Solution code:
def main():
    n, p = map(int, input().split())
    s = list(map(int, list(input())))
    now = 1
    now2 = 0

    dp = [0]*p
    cnt = 0
    if p != 5:
        for i in s:
            now2 = (now2*10+i) % p
            dp[((i-now2) % p)*pow(now, p-2, p) % p] += 1
            cnt += dp[((-now2) % p)*pow(now, p-2, p) % p]
            now = (now*10) % p
    else:
        for j, i in enumerate(s):
            if i in [0, 5]:
                cnt += j+1
    print(cnt)


main()

Submission status: Accepted

Solution code:
def solve(n, p, s):
    res = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p == 0:
                res += i + 1
        return res

    mod_count = [0] * p
    temp = 0
    pow_10_i_p = [0] * n
    pow_10_i_p[0] = 1
    for i in range(1, n):
        pow_10_i_p[i] = pow_10_i_p[i - 1] * 10 % p
    for i in range(n):
        temp = (temp + pow_10_i_p[i] * int(s[-(i + 1)])) % p
        mod_count[temp] += 1
    res += mod_count[0]
    for i in range(p):
        res += mod_count[i] * (mod_count[i] - 1) // 2
    return res


def main():
    n, p = map(int, input().split())
    s = input()
    res = solve(n, p, s)
    print(res)


def test():
    assert solve(4, 3, "3543") == 6
    assert solve(4, 2, "2020") == 10
    assert solve(20, 11, "33883322005544116655") == 68


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

if P == 2 or P == 5 :
  ret = 0
  for i, v in enumerate(S) :
    if int(v) % P == 0 :
      ret += i + 1
  print(ret)

else :
  mem = defaultdict(int)
  mem[0] += 1

  T = [0]
  dec = 1
  x = 0
  for s in S[::-1] :
    s = int(s)
    x = (dec * s + x) % P
    dec = dec * 10 % P
    T.append(x)
    mem[x] += 1

  ret = 0
  for i, t in enumerate(T) :
    ret += mem[t] - 1
    mem[t] -= 1
    
  print(ret)

Submission status: Accepted

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

  ans = 0

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

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

  rem_list = [0] * p
  cof = 1
  prev_rem = 0
  
  for i in range(n):
    rem = (int(s[n-1-i]) * cof + prev_rem) %  p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

    prev_rem = rem
    cof *= 10
    cof %= p

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import Counter

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

if p == 2 or p == 5:
    ans = 0
    for i, e in enumerate(s, 1):
        if int(e) % p == 0:
            ans += i

    print(ans)

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

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

rem=[0]*p
remls=[0]*n
remnow=0
for i in range(n-1,-1,-1):
    remnow = (remnow+int(s[i])*pow(10, n-1-i, p))%p
    rem[remnow]+=1
    remls[i]=remnow

ans=0
remnow2=0
remdiff=1
for i in range(n-1,-1,-1):
    remdiff2=(remdiff-remnow2)%p
    idx=-remnow2*pow(remdiff2,p-2,p)%p
    ans+=rem[idx]
    remnow2-=int(s[i])
    remnow2%=p
    remnow2*=pow(10,p-2,p)
    remnow2%=p
    remdiff-=int(s[i])
    remdiff%=p
    remdiff*=pow(10,p-2,p)
    remdiff%=p
    rem[remls[i]]-=1

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

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


print(ans)