Problem:


Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

1 \leq N \leq 2 \times 10^5

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Accepted

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

else:
	mods = [0 for _ in range(p)]
	cur = 0
	mods[0] += 1
	t = s[::-1]
	for i in range(n):
		cur = (cur + int(t[i]) * pow(10, i, p)) % p
		mods[cur] += 1
	#print(mods)
	ans = 0
	for m in mods:
		ans += (m * (m-1)) // 2
	print(ans)

Submission status: Accepted

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

S = S[::-1]

if P!=2 and P!=5:

    current = 1

    SP = []

    for i in range(N):
        SP.append((int(S[i])*current)%P)
        current*=10
        current%=P

    SSP = [0]
    s = 0
    for i in range(N):
        s+=SP[i]
        s%=P
        SSP.append(s)

    from collections import Counter

    counter = Counter(SSP)
    ans = 0
    for key in counter:
        ans += (counter[key]*(counter[key]-1))//2

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

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:
from collections import Counter
from itertools import accumulate
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
  print(ans)
elif p == 5:
  ans = 0
  for i in range(n):
    if int(s[i])%5 == 0:
      ans += i+1
  print(ans)
else:
  ls = [0]
  prev = 0
  for i in range(n):
    x = int(s[n-i-1])
    y = (prev+x*pow(10,i,p))%p
    ls.append(y)
    prev = y
  c = Counter(ls)
  ans = 0
  for x in c.values():
    ans += x*(x-1)//2
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
 
rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m
 
def solve(N, P, S):
    A = map(int, S)
    if P == 2 or P == 5:
        ans = 0
        for i, x in enumerate(A):
            if x % P == 0:
                ans += i + 1
        return ans

    powers = [0] * N
    pwr = 1
    for i in xrange(N-1, -1, -1):
        powers[i] = pwr
        pwr *= 10; pwr %= P

    #Xinv = modinv(10, P)
    count = Counter()
    count[0] += 1
    s = 0
    ans = 0
    for i in xrange(N-1, -1, -1):
        w = A[i] * powers[i] % P
        s += w; s %= P
        ans += count[s]
        count[s] += 1
        #print("!", ans)
    return ans
 
 
N, P = rrm()
print solve(N, P, rr())

Submission status: Accepted

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

n,p = [int(i) for i in readline().split()]
s = input()

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



res = [0]*p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i*t
    now %= p
    res[now] += 1
    t = t*10%p

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

print(ans)

Submission status: Accepted

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

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


a = [0]
j = n-1
for i in s:
    a.append((a[-1] + int(i) * pow(10, j, p))%p)
    j -= 1

b = {}
for i in a:
    if i in b:
        b[i] += 1
    else:
        b[i] = 1
ans = 0
for i in b:
    ans += b[i] * (b[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, p = na()
s = ns()

if p != 2 and p != 5:
    a = []
    t = 1
    for i in range(n-1, -1, -1):
        a.append((ord(s[i])-ord("0")) * t % p)
        t = t * 10 % p
    cum = [0]
    for v in a:
        cum.append((cum[-1] + v) % p)

    dic = defaultdict(int)
    ans = 0
    for v in cum:
        ans += dic[v]
        dic[v] += 1
    print(ans)
elif p == 2:
    ans = 0
    for i in range(n):
        if (ord(s[i]) - ord("0")) % 2 == 0:
            ans += i+1
    print(ans)
else:
    ans = 0
    for i in range(n):
        if (ord(s[i]) - ord("0")) % 5 == 0:
            ans += i+1
    print(ans)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

def getCharNGram(n,s):
    charGram = [str(int(''.join(s[i:i+n]))) for i in range(len(s)-n+1)]
    return charGram

n, p = na()
s = ns()
ct = 0
amari = [0] * (n+1)
amari[0] = 10 % p
for i in range(1, n):
    amari[i] = (amari[i-1] * 10) % p
for i in range(1, n+1):
    li = getCharNGram(i,s)
    for c in li:
        ls = 0
        for j in range(i):
            ls += amari[j] * int(c[j])
        if ls % p == 0:
            ct += 1
print(ct)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

ans = 0
if p in {2, 5}:
    for i, num in enumerate(s):
        if num % p == 0:
            ans += i + 1
else:
    modp = [0]
    for num in s[::-1]:
        tmp = modp[-1] + pow(10, i, p) * num
        modp.append(tmp % p)
    cnt = [0] * p
    for i in modp:
        ans += cnt[i]
        cnt[i] += 1
print(ans)

if p == 3:
    print('hoge')

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
import numpy as np
import sys
sys.setrecursionlimit(10**9)


INF=10**20
def solve(N,P,S):
    ans = 0

    # print(S)
    # print(S[0])
    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0
 
        d[0] = 1
        for i in range(N):
            s += S[N-i-1] * 10**i % P
            s %= P
            s = int(s)
            # print(s)
            d[s] += 1
 
        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2
 
    else:
        for i in range(N):
            if S[i] % P == 0:
                ans += i+1

 
    return ans

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 = list(next(tokens))  # type: str

    S = list(map(int,S))
    S = np.array(S)
    print(solve(N, P, S))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    # try:
    #     from my_module import solve
    # except:
    #     cc_export()
    #     exit()

    main()

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = input()
lst = [0] * p
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:
  q = 0
  for i in range(n-1, -1, -1):
    if int(s[i]) != 0
      num = int(s[i]) * 10 ** (n - i - 1)
    else:
      num = 0
    q += num % p
    if q >= p:
      q -= p
    lst[q] += 1
  lst[0] += 1
  for i in range(p):
    value = lst[i]
    if value > 1:
      count += value * (value - 1) // 2
  print(count)

Submission status: Runtime Error

Solution code:
import java.util.*;
import java.io.*;

public class Main {

    private final static int MOD = 998244353; // (int)1e9 + 7;
    private static final int INF = (int)1e9;

    public Main(FastScanner in, PrintWriter out) {
        int n = in.nextInt();
        int p = in.nextInt();
        String s = in.next();
        int[] cnt = new int[p + 1];
        cnt[0] = 1;
        int cur = 0, f = 1;
        long res = 0;
        for (int i = n - 1; i >= 0; i--) {
            int d = s.charAt(i) - '0';
            cur = (f * d + cur) % p;
            res += cnt[cur];
            cnt[cur]++;
            f = f * 10 % p;
        }
        out.println(res);
    }

    private int gcd(int a, int b) {
        while (true) {
            if (b == 0) return a;
            int tmp = a;
            a = b;
            b = tmp % b;
        }
    }

    private long powm(long x, long p) {
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1)
                res = res * x % MOD;
            x = x * x % MOD;
            p /= 2;
        }
        return res;
    }


    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        // Scanner in = new Scanner(
                // new BufferedReader(new InputStreamReader(System.in)));
        FastScanner in = new FastScanner(System.in);

        Main sol = new Main(in, out);

        out.close();
    }
}


class FastScanner{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }

    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }

    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

    long nextLong()
    {
        return Long.parseLong(next());
    }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }

    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}

Submission status: Runtime Error

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

amari=[0]*P
amari[0]=1

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

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

for i in range(1,N+1):
  amari[int(S[-i:])%P]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

Submission status: Runtime Error

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

amari=[0]*P
amari[0]=1

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

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

for i in range(1,N+1):
  amari[int(S[-i:])%P]+=1
ans=0
for tmp in amari:
  ans+=tmp*(tmp-1)//2
  
print(ans)

Submission status: Runtime Error

Solution code:
"""
タグ：区間
"""
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
S = input()

if P == 5:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%5==0:
            res += N-i
        i += 1
    print(res)
elif P == 2:
    res = 0
    i = 0
    for s in reversed(S):
        if int(s)%2==0:
            res += N-i
        i += 1
    print(res)
else:
    T = [0]
    p = 1
    for s in reversed(S):
        T.append(int(s)*p + T[-1])
        p = p*10%P

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

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

Submission status: Runtime Error

Solution code:
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:
    s=s[::-1]
    M=[0]*n
    M[0]=1
    tmp=0
    for i in range(n):
        tmp+=((int(s[i])*10**i)%p)
        ans+=M[tmp%p]
        M[tmp%p]+=1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(n):
    for j in range(n+1):
        if i >= j :
            continue
        else:
            if p == 2 or p == 5:
                if int(s[n])%p == 0:
                    cnt += 1
            else:
                if (j-i) == 1:
                    a = int(s[i:j])%p
                else:
                    a = (a*10 + int(s[j-1]))%p
                if a == 0:
                    cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = input().strip("\n")
    modSum = 0
    modSum = int(S[0]) % P
    modDict = defaultdict(int)
    ans = 0

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

        for key in modDict:
            v = modDict[key]
            if key > 0: ans += v * (v - 1) // 2
            else: ans += v + (v * (v - 1) // 2)
    
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n,p = map(int,input().split())
s = list(map(int,list(input())))[::-1]
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p==0:
            ans += n-i
    print(ans)
else:
    d = defaultdict(int)
    check = 0
    for i in range(n):
        check += s[i]*10**i
        check %= p
        ans += d[check]
        if check == 0:
            ans+=1
        d[check] += 1
        ten += 1
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
DP=[0]

if p==2 or p==5:
    if s[0]%p==0:print(n*(n+1)//2)
    else:print(0)
else:
    num,point=0,1
    for i in s:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p
    
    ans=0
    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
    print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = S[::-1]
    primdic = defaultdict(int)
    before = 0
    for i in range(0,N):
        now = (S[i]*pow(10,i,P)+before)%P
        primdic[now] += 1
        before = now
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    #primdic = defaultdict(int)
    primdic = [0]*N
    for i in range(N):
        # i~右端までの数字のmodP
        primdic[int(S[i:])%P] += 1
    primdic[0] += 1
    ans = 0
    #for value in primdic.values():
    #    ans += value*(value-1)//2
    for value in primdic:
        ans += value*(value-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
N,P = map(int,input().split())
S = input()
S_li = [0]*(N+1)
S_rev = reversed(S)
counter = 0
tmp = 0
count= 0
from  collections import Counter

if 10%P==0:
    for i,num in enumerate(S_rev):
        if num==str(P) or num=="0":
            counter += N-i
    print(counter)

else:
    ctr = [0] * P
    ctr[0] = 1
 
    ret = 0
    t = 0
    c = 1
    for x in S_rev:
        t = (t + c * x) % P
        ret += ctr[t]
        ctr[t] += 1
        c = c * 10 % P
 
    print(ret)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

s = int(input())

a = 0
t = []

while s > 0:
    d = s // 10
    r = s % 10
    t.append(r)
    s = d

if p == 2:
    for i in range(len(t)):
        if t[i] % 2 == 0:
            a += len(t) - i 
elif p == 5:
        if t[i] % 5 == 0:
            a += len(t) - i 

else:
    u = []
    k = 1
    for i in range(len(t)):
        if i == 0:
            u.append(t[i]*k % p)
        else:
            u.append((u[i-1] + t[i]*k) % p)
        k *= 10
    c = Counter(u)

    a += c[0]
    for i in c.values():
        if i > 1:
            a += i * (i-1) // 2


print(a)

Submission status: Runtime Error

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

s = int(input())

a = 0
t = []

while s > 0:
    d = s // 10
    r = s % 10
    t.append(r)
    s = d

if p == 2:
    for i in range(len(t)):
        if t[i] % 2 == 0:
            a += len(t) - i 
elif p == 5:
        if t[i] % 5 == 0:
            a += len(t) - i 

else:
    u = []
    k = 1
    for i in range(len(t)):
        u.append(t[i]*k % p)
        k *= 10

    for i in range(len(u)):
        for j in range(i, len(u)):
            if sum(u[i:j+1]) % p == 0:
                a += 1

print(a)

Submission status: Runtime Error

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

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

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

else:
    mod = 0
    c = [0] * p
    c[0] = 1
    ten = 1
    for i in s:
        mod = (mod + ten * int(i)) % p
        ten = ten * 10 % p
        c[mod] += 1

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

Submission status: Runtime Error

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]) * 10**i) % p
        ten = ten * 10 % p
        count[mod] += 1
        out += (c * (c - 1)) // 2
print(out)

Submission status: Runtime Error

Solution code:
N,P = map(int,input().split())
S=input()
mem_mod = [0 for i in range(0,2019,1)]
counter = 0
S_num = list(map(int, S))
tmp=10

for i in range(1,N,1):
    S_num[N-i-1] = S_num[N-i] + S_num[N-i-1]*pow(10,i,P)

for i in range(0,N,1):
    X = S_num[N-i-1] % P
    if X==0:
        counter+=1
    counter += mem_mod[X]
    mem_mod[X] += 1
print(counter)

Submission status: Runtime Error

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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from math import pow
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: Runtime Error

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

MOD = p

mods = [0 for _ in range(2019)]
mods[0] = 1

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

print(ans)

Submission status: Runtime Error

Solution code:
a,b= map(int, input().split())
n = int(input())
countArray = [0] * b
count = 0
countArray[0] += 0
nums = 0


for i in range(a):
    nums = nums + int(str(n)[a-1-i])*pow(10,i)
    countArray[nums % b] += 1
    if nums % b == 0:
        count +=1

for i in countArray:
    count += (i * (i - 1)) // 2
print(count)

Submission status: Runtime Error

Solution code:
a,b= map(int, input().split())
n = int(input())
countArray = [0] * b
count = 0
countArray[0] += 0
nums = 0


for i in range(a):
    nums = nums + int(str(n)[a-1-i])*pow(10,i,b)
    countArray[nums % b] += 1
    if nums % b == 0:
        count +=1

for i in countArray:
    count += (i * (i - 1)) // 2
print(count)

Submission status: Runtime Error

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: Runtime Error

Solution code:
from collections import Counter

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:
        D = [0] * (N+1)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = 0
        for i in c.values():
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

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:
        D = [0] * (N+1)
        for i in range(N):
            D[i] =  int(S[:i+1][::-1]) % P
        C = Counter(D)
        ans = sum([max(c*(c-1)//2 for c in C.values()])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

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]*(n+1)
  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(n):
    ans += mods[i]*(mods[i]-1)//2

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

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]*(n+1)
  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+1):
    ans += mods[i]*(mods[i]-1)//2

print(ans)

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
l = [0] * n
cur_base = 0
ans = 0
k = 1
for d in map(int, reversed(input())):
    l[cur_base] += 1
    cur_base = (cur_base - d * k) % p
    k = k * 10 % p
    ans += l[cur_base]
print(ans)