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 = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i
           
else:
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2


print(ans)

Submission status: Accepted

Solution code:

def main():
    N,P = map(int,input().split())
    s = list(input())[::-1]
    ary_mod = [0] * P
    ary_mod[0] = 1
    now = 0
    digit = 1
    ans = 0
    if P == 2:
        for i, ss in enumerate(s):
            if int(ss) % 2 == 0:
                ans += N-i
        print(ans)
        return
    if P == 5:
        for i, ss in enumerate(s):
            if int(ss) % 5 == 0:
                ans += N-i
        print(ans)
        return

    for i, ss in enumerate(s):
        now += int(ss) * digit % P
        digit *= 10
        digit %= P
        remind = now % P
        ary_mod[remind] += 1
    ans = 0
    for i, n in enumerate(ary_mod):
        ans += (n*(n-1)) // 2
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

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

        else:
            mods = [0] * P  # mods[i]はPで割ったあまりがiである連続部分列の個数
            tenfactor = 1
            mod = 0
            mods[mod] += 1

            for i in range(N):
                mod = (mod + int(S[N - i - 1]) * tenfactor) % P
                tenfactor = (tenfactor * 10) % P
                mods[mod] += 1

            res = 0
            for p in range(P):
                res += mods[p] * (mods[p] - 1) // 2

        return res

    print(main())


resolve()

Submission status: Accepted

Solution code:
from collections import Counter

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

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

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

print(ans)

Submission status: Accepted

Solution code:
# Problem E - Divisible Substring

from collections import Counter

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = 0
    for i in range(N-1, -1, -1):
        s = int(S[i]) * pow(10, N - i - 1, P) + s
        p_nums[N - i] = s%P
    p_counter = [0]*P
    for i in range(N+1):
        p_counter[p_nums[i]] += 1
    ans = 0
    for i in range(P):
        ans += p_counter[i] * (p_counter[i] - 1) // 2
    print(ans)

Submission status: Accepted

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

if P == 2 or P == 5:
    cnt = 0

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = 0

    for i, s in enumerate(S[::-1]):
        num  = (num + int(s) * pow(10, i, P)) % P
        cnt += r_lst[num]

        r_lst[num] += 1


print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,P=map(int,input().split())
    A=list(map(int,list(input())[::-1]))
    ans=0
    if P==2 or P==5:
        if P==2:
            s=set([i*2 for i in range(5)])
        else:
            s=set([i*5 for i in range(2)])
        for i,x in enumerate(A[::-1],1):
            if x in s:
                ans+=i
    else:
        S=[0]*(N+1)
        for i in range(N):
            S[i+1]=(S[i]+A[i]*pow(10,i,P))%P
        l=[0]*P
        for i in range(N+1):
            ans+=l[S[i]]
            l[S[i]]+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
s=1817181712114 なら
4
10
100
2000
10000
700000
1000000
80000000
100000000
7000000000
10000000000
800000000000
1000000000000
の数列とみて, 各々%Pを取ってzero sum range
P=2,5がコーナー
"""
from collections import Counter
def make_modlist(Len,mod):
    modlist=[0]*Len
    modlist[0]=1
    for i in range(1,Len):
        modlist[i]=10*modlist[i-1]%mod
    return modlist
n,p=map(int,input().split())
a=list(map(int,input()))
ans=0
a.reverse()
if p==2 or p==5:
    for i in range(n):
        if a[i]%p==0:
            ans+=n-i
else:
    d=make_modlist(n,p)
    b=[0]*(n+1)
    for i in range(n):
        b[i+1]=a[i]*d[i]%p
    for i in range(1,n+1):
        b[i]+=b[i-1]
        b[i]%=p
    for i in Counter(b).values():
        ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,MOD=map(int,input().split())
S=input()
res=0
if MOD==2 or MOD==5:
    for i in range(N):
        if(int(S[N-i-1])%MOD==0):
            res+=N-i
else:
    Cum=[0]*(N+1)
    for i in range(N):
        Cum[i+1]=(Cum[i]+int(S[N-i-1])*pow(10,i,MOD))%MOD
    c=Counter(Cum).most_common()
    for a,b in c:
        res+=b*(b-1)//2
print(res)

Submission status: Accepted

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = [0]*p
    d[0] = 1 # 0(mod p)はそれ単体で割り切れるため+1しておく
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = (10*x)%p # %p無しだとTLE
    cnt = 0
    for di in d:
        cnt += di*(di-1)//2 # calc combination(n_C_2)
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
ten = 1
d = 0

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

else:
    cntlist = [0]*p
    cntlist[0] = 1
    for i in range(n-1,-1,-1):
        a = int(s[i])*ten%p
        d = (d + a)%p
        ten *= 10
        ten %= p
        cntlist[d] += 1

    for i in cntlist:
        ans += i*(i-1)//2
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
r=1
su=0
dd[0]=1
if p==2 or p==5:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)
else:
    for s in S[::-1]:
        tmp+=int(s)*r
        tmp%=p
        dd[tmp]+=1
        r*=10
        r%=p
    for i in dd.values():
        su += (i*(i-1))//2
    print(su)

Submission status: Accepted

Solution code:
import sys
n,p=map(int,input().split())
s=list(input())
if p==2 or p==5:
    ans=0
    for i in range(n):
        if int(s[i])%p==0:
            ans+=i+1
    print(ans)
    sys.exit(0)
ans=0
count=[0]*p
count[0]=1
s=s[::-1]
num=0
seki=1
for i in range(n):
    num+=int(s[i])*seki
    num=num%p
    count[num]+=1
    seki=seki*10
    seki=seki%p
for i in range(p):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)
#print(count)

Submission status: Accepted

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = {i: 0 for i in range(p)}
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = 10*x%p
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

r = [0]*p
r[0] = 1
t = 1
z = 0
for i in reversed(s):
    z = int(i) * t + z
    t *= 10
    t %= p
    z %= p
    r[z] += 1

ans = sum(i*(i-1)//2 for i in r)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N, P = map(int, readline().split())
    S = [int(i) for i in readline().strip()[::-1]]

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

    a = {}
    a[0] = 1
    t = 0
    x = 1
    for s in S:
        t += s * x
        t %= P
        
        if t in a:
            a[t] += 1
        else:
            a[t] = 1

        x *= 10
        x %= P
    
    ans = 0
    for v in a.values():
        ans += v * (v-1) // 2
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if P in [2, 5]:
  ans = 0
  for i, s in enumerate(S, 1):
    if int(s) % P == 0:
      ans += i
  print(ans)
else:
  dp = [0] * (N+1)
  for i, s in enumerate(S, 1):
    dp[i] = (dp[i-1]*10 + int(s)) % P
  digit = 1
  for i in range(N):
    j = N - i
    dp[j] = (dp[j] * digit) % P
    digit = (digit * 10) % P
  
  d = {}
  ans = 0
  for r in dp:
    if r in d:
      ans += d[r]
      d[r] += 1
    else:
      d[r] = 1
  print(ans)

Submission status: Accepted

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

def main():
    N, P = map(int, readline().split())
    S = [int(i) for i in readline().strip()[::-1]]

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

    a = [0]
    s = 0
    for i in range(N):
        s += S[i] * pow(10, i, P)
        a.append(s % P)
    
    t = Counter(a)

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

    


if __name__ == "__main__":
    main()

Submission status: Accepted

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


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

Submission status: Accepted

Solution code:

def resolve():
    l, P = map(int, input().split())
    S = input()

    ans = 0
    # 10^r: 2^r * 5^r の為、10と同じ素数
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += i + 1
        return print(ans)

    cnts = [0] * P
    cnts[0] = 1
    num, d = 0, 1
    for s in S[::-1]:
        s = int(s)
        num = (num + (s * d)) % P
        d = (10 * d) % P
        cnts[num] += 1

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

if P%2 == 0 or P%5 == 0:
    ans = 0
    ##S = S[::-1]
    for i,j in enumerate(S):
        if int(j)%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter

n, p = map(int, readline().split())
s = readline().rstrip().decode()
cnt = 0
if p == 2 or p == 5:
    for i, ss in enumerate(s):
        if int(ss) % p == 0:
            cnt += (i + 1)
else:
    memo = [0]
    m = 0
    d = 1
    for ss in s[::-1]:
        m += int(ss) * d
        m %= p
        d *= 10
        d %= p
        memo.append(m)
    counter = Counter(memo)
    for i in range(p + 1):
        cnt += counter[i] * (counter[i] - 1) // 2
print(cnt)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
S = [int(i) for i in input()]
from collections import Counter
def solve(S,N,P):
    if P==2 or P==5:
        ans = 0
        for i in range(N):
            if S[i]%P==0:
                ans += i+1
        return ans
    cum = [0]*(N+1)
    mods = [0]*N
    mods[0] = 1
    for i in range(1,N):
        mods[i] = mods[i-1]*10%P
    for i in range(N):
        cum[i+1] = (cum[i]+S[N-1-i]*mods[i])%P
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S,N,P))

Submission status: Accepted

Solution code:
N,P=[int(s) for s in input().split()]
S=list(input())
if P!=2 and P!=5:
  ls=[0 for _ in range(N)]
  mod=[0 for _ in range(P)]
  d=10
  ls[0]=int(S[-1])%P
  mod[ls[0]]+=1
  for i in range(1,N):
    ls[i]=(ls[i-1]+d*int(S[-1-i]))%P
    d=(d*10)%P
    mod[ls[i]]+=1
  #print(ls)
  #print(mod)  
  ans=mod[0]
  for i in range(N):
    m=ls[i]
    mod[ls[i]]-=1
    ans+=mod[ls[i]]
else:
  ans=0
  for i in range(N):
    if int(S[i])%P==0:
      ans+=i+1
print(ans)

Submission status: Accepted

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

count = [0]*p

key = 0
if p%2 and p%5:
  count = [0]*p
  key = 0
  
  mod = 1
  for i in range(n):
    key += (mod*int(s[n-1-i]))%p
    key %= p
    count[key] += 1
    mod *= 10
    mod %= p
  ans = count[0]
  for i in range(p):
    if count[i] >= 2:
      ans += (count[i])*(count[i]-1)//2
else:
  ans = 0
  for i in range(n):
    key = int(s[n-1-i])
    if key%p == 0:
      ans += n-i
print(ans)

Submission status: Accepted

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

def solve(S,N,P):
    if P == 2:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    if P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    
    S = S[::-1]
    mod_list = [0]*P
    mod_list[0] = 1

    mod = P
    tmp = 0

    for i in range(N):
        tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
        mod_list[tmp] += 1
    
    ans = 0
    for i in mod_list:
        ans += i*(i-1)//2
        
    return ans

print(solve(S,N,P))

Submission status: Accepted

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

XX = 0
if P == 2:
    for i in range(N):
        if int(S[i]) % 2 == 0:
            XX += i + 1
    print(XX)
elif P == 5:
    for i in range(N):
        if int(S[i]) % 5 == 0:
            XX += i + 1
    print(XX)
else:
    base = 1
    X = [0 for i in range(N)]
    X[-1] = int(S[-1])
    for i in range(N, 0, -1):
        X[i-1] = (base * int(S[i-1])) % P
        base *= 10
        base %= P
    for i in range(1, N):
        X[i] += X[i-1]
        X[i] %= P
    D = {i: 0 for i in range(P)}
    D[0] = 1
    for i in range(N):
        D[X[i]] += 1
    XX = 0
    for i in D:
        XX += (D[i] * (D[i] - 1)) // 2
    print(XX)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,p = map(int,input().split())
s=input()
ans = 0
l = [0 for i in range(p)]
l[0] = 1
z = 0
ten = 1
tmp = 0
if p == 2 or p == 5:
    if p == 2:
        for i in range(n):
            if int(s[i])%2 == 0:
                ans+=i+1
    if p == 5:
        for i in range(n):
            if int(s[i])%5 == 0:
                ans+= i+1
    
else:
    for i in s[::-1]:
        i = int(i)
        tmp=(tmp+i*ten)%p
        ten = (ten*10)%p
        l[tmp]+=1
for i in l:
    ans+= i*(i-1)//2
print(ans)

Submission status: Accepted

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

n, p = [int(x) for x in input().split()]
s = input().rstrip()[::-1]
ans = 0
if p == 2:
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += (n - i)
    print(ans)
    sys.exit()
if p == 5:
    for i in range(n):
        if int(s[i]) == 0 or int(s[i]) == 5:
            ans += (n - i)
    print(ans)
    sys.exit()
t = [0, int(s[0]) % p]
mul = 10
for i in range(1, n):
    t.append((t[-1] + int(s[i])*mul) % p)
    mul *= 10
    mul %= p
from collections import Counter
c = Counter(t)
for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2
print(ans)

Submission status: Accepted

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

#累積和を求めるため後ろから処理したい。配列は逆転しておく。
revS = S[::-1] 


# 10が素数であまり0、つまり2か5の場合
# 区間の下1けた目の数によって、どれだけ左側に伸ばして行っても
# 必ず割り切れる
if(10 % P == 0):
  res = 0

  for index, num in enumerate(revS):
    if(int(num) % P == 0) :
      res += len(revS) - index

  print(res)

else:

  #累積和を入れておく
  cs = 0

  ## あまりの値のカウント
  counts = [0] * P

  ## 累積和の初項は0になる
  ## 余りの値をindexにして配列 counts に同じ余りの値の個数を記録するので
  ## 初項の分は先に処理しておく
  counts[cs] += 1

  ## 桁
  d = 1

  ## 2項目からはfor文を使って同じ余りの値のカウントを行う処理する
  for num in revS:
    m = (int(num) * d) % P
    cs = (cs + m) % P

    counts[cs] += 1

    # 次の桁へ移動
    d *= 10

    # 桁が巨大になりすぎるのであまりを撮っておく
    # 掛け算の最中にあまりを撮るのは問題ない
    d %= P

  res = 0

  for n in counts:
    # 同じ余りの値がn個あったとして、重複なく2つ取り出す方法はnC2個
    res += n * (n - 1) // 2

  print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, mod = mi()
S = list(map(int, list(input())))
ans = 0

if 10 % mod != 0:
    mod_list = [0]
    ten = 1
    for num in S[::-1]:
        yo = (num * ten + mod_list[-1]) % mod
        mod_list.append(yo)
        ten = (ten * 10) % mod

    cnt = [0]*mod
    for yo in mod_list:
        cnt[yo] += 1

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

else:
    for i, num in enumerate(S):
        if num % mod == 0:
            ans += i+1

print(ans)

Submission status: Accepted

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = [0]*P
    mod_cnt[0] = 1
    k = 0.1
    t = 0
    for i in range(1, N+1):
        k = int(k * 10) % P
        t = (t + k * int(S[-i])) % P
        mod_cnt[t] += 1
    ans = 0
    for cnt in mod_cnt:
        ans += (cnt * (cnt-1)) // 2
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

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

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1

    for d in D:
        cnts[d] += 1

    for i in cnts:
        ans += i * (i - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

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

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        cnts[D[i]] += 1
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1

    for i in cnts:
        ans += i * (i - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
s = input()
rem = [0 for i in range(p)]
total = 0
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:
    for i in range(len(s)-1, -1, -1):
        total += int(s[i])*pow(10, len(s)-i-1, p)
        total %= p
        if total % p == 0:
            ans += 1
        ans += rem[total]
        rem[total] += 1

    print(ans)

Submission status: Accepted

Solution code:
import sys

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


def input():
    return sys.stdin.readline().strip()


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

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  n,p=map(int,input().split())
  s=input()
  if 10%p==0:
    print(sum(i for i,x in enumerate(s,1) if int(x)%p==0))
    exit()
  s=s[::-1]
  x=[0]*p
  x[0]=1
  a,t=0,1
  for i in range(n):
    a=(a+int(s[i])*t)%p
    x[a]+=1
    t=(t*10)%p
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
s=input()
if 10%p==0:
  print(sum(i for i,x in enumerate(s,1) if int(x)%p==0))
  exit()
ans=0
u=0
d=1
l=[0]*p
l[0]=1
s=s[::-1]
for i in map(int,s):
  u=(u+i*d)%p
  l[u]+=1
  d=d*10%p
for i in l:
  ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

def two_or_five():
    global S,N,P
    ans = 0
    for k,v in enumerate(S):
        v = int(v)
        if v % P:
            continue
        ans += k + 1
    return ans

def other():
    global S,N,P
    S = reversed(S)
    T = [0] * N
    a = 1
    for k,v in enumerate(S):
        T[k] = T[k-1] + a * int(v)
        T[k] %= P
        a *= 10
        a %= P
    T.append(0)
    ans = 0
    for k,v in Counter(T).items():
        ans += v * (v-1) // 2
    return ans

if P in {2,5}:
    print(two_or_five())
else:
    print(other())

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,p = get_nums_l()
s = input()
X = list(map(int, list(s)))
n = len(s)

if p in (2,5):
    ans = 0
    for i,x in enumerate(X):
        if x%p == 0:
            ans += i+1
    print(ans)
else:
    ruiseki = [0] * (n+1)
    for i in (range(n-1, -1, -1)):
        ruiseki[i] = (X[i] * pow(10, (n-i-1), p) + ruiseki[i+1]) % p

    # log(ruiseki)

    ans = 0
    count = defaultdict(int)

    for x in ruiseki:
        # log(count[x])
        ans += count[x]
        count[x] += 1
    # log(count)
    print(ans)

Submission status: Accepted

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

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



else:
    res = 0
    cnt = [0] * p
    for i in range(n):
        res = (res + int(s[n-1-i]) * pow(10, i, p)) % p
        cnt[res] += 1

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

Submission status: Accepted

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


def solve(N: int, P: int, S: str):

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

    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*int(S[i])
        a %= P
        U[i] = a
        beki = (beki * 10) % P
    table = [0]*P
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    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 = str(next(tokens))  # type: int
    solve(N, P, S)


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:
from collections import defaultdict as dict

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

def solve():
    l = [0]*p
    ans = 0
    for x in a:
        l_ = [0] * p
        for i in range(p):
            l_[(i * 10 + x) % p] += l[i]
        l, l_ = l_, l
        l[x % p] += 1
        ans += l[0]

    print(ans)
if p <= 5:
    solve()
    exit()
x = 0
mem = dict(int)
mem[0] = 1
ans = 0
a.reverse()
d = 1
for y in a:
    x += d*y
    x %= p
    d = (d * 10) % p
    ans += mem[x]
    mem[x] += 1
    # print(mem)

print(ans)