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: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += len(S[:j])
    else:
        S = S[::-1]
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    ans += len(S[i:i+j])
    else:
        S = S[::-1]
        d = 1
        acc = [0]*(N+1)
        for i, s in enumerate(S):
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def make_num(s):
    num = []
    for i in range(1,n+1): #桁数を指定
        #num_bef = []
        for j in range(n): #先頭の要素を指定
            num_bef = []
            for k in range(j,j + i):
                if j + i > n:
                    continue
                else:
                    num_bef.append(s[k])
            num_bef1 = ''.join(num_bef)
            num.append(num_bef1)
        #print(num)
    return num

if __name__ == '__main__':
    count = 0
    num_list = make_num(s)
    #print(num_list)
    for a_num in num_list:
        if a_num == '':
            continue
        else:
            if int(a_num) % p == 0:
                #print(a_num)
                count += 1
    print(count)

Submission status: Time Limit Exceeded

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

def twofive(n, p, s):
    res = 0
    for i in range(n):
        mostlow = int(s[i])
        if mostlow%p==0:
            res += i+1
    return res

def others(n, p, s):
    from collections import Counter
    res = 0
    
    s = s + '0'
    amari = []
    for i in range(len(s)):
        ak = int(s[i:])
        amari.append(ak%p)
    
    amaricnt = Counter(amari)
    for val in amaricnt.values():
        if val == 1:
            continue
        else:
            res += val*(val-1)//2
    
    return res

if p == 2 or p==5:
    print(twofive(n, p, s))
else:
    print(others(n, p, s))

Submission status: Time Limit Exceeded

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

    ans = 0
    if P == 5 or P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    ans += len(S[i:i+j])
    else:
        S = S[::-1]
        d = 1
        acc = [0]*(N+1)
        for i, s in enumerate(S):
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        from collections import Counter
        c = Counter(acc)
        # print(acc, c)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    if P == 5 or P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    else:
        from itertools import accumulate
        S = S[::-1]
        d = 1
        acc = [0]*N
        for i, s in enumerate(S):
            s = int(s)
            acc[i] = (s * d) % P
            d *= 10
            d %= P
        acc = list(accumulate([0] + acc))
        acc = [a % P for a in acc]
        from collections import Counter
        c = Counter(acc)
        # print(acc, c)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit(0)

surpluses = [0] * P
s = 0
power = 1
for i in range(N):
    s += int(S[-1-i]) * power
    surpluses[s % P] += 1
    power *= 10

ans = surpluses[0]
for count in surpluses:
    ans += count * (count - 1) // 2

print(ans)

Submission status: Time Limit Exceeded

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

# process
ans = 0
pmod = 0
for i in range(N-1):
    mod = int(S[i])%P
    if mod == 0:
        ans += 1
    pmod = mod

    for j in range(i+1, N):
        mod = (int(S[j])+pmod*10)%P
        if mod == 0:
            ans += 1
        pmod = mod

if int(S[-1])%P == 0:
    ans += 1

# output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P=map(int, input().split())
S=input()
dp=[[0]*P for _ in range(N)]
dp[0][int(S[0])%P]=1
for i in range(1, N):
  tmp=S[i]
  dp[i][int(tmp)%P]+=1
  for j in range(P):
    dp[i][int(str(j)+tmp)%P]+=dp[i-1][j]
print(sum([dp[i][0] for i in range(N)]))

Submission status: Time Limit Exceeded

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

    ans = 0
    if P == 5 or P == 2:
        for i in range(1):
            for j in range(1, N-i+1):
                num = int(S[i:i+j])
                if num % P == 0:
                    # print("!", end=" ")
                    ans += len(S[i:i+j])
                # print(num)
    else:
        from itertools import accumulate
        S = S[::-1]
        acc = [(int(s)*10**i) % P for i, s in enumerate(S)]
        acc = list(accumulate([0] + acc))
        acc = [a % P for a in acc]
        from collections import Counter
        c = Counter(acc)
        # print(acc, c)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit(0)

suf_nums = [-1] * N
s = 0
power = 1
for i in range(N):
    s += int(S[-1-i]) * power
    suf_nums[i] = s
    power *= 10

surpluses = [0] * P
ans = 0
for num in suf_nums:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,p = map(int, input().split())
s = input()

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

u = defaultdict(int)
u[0] = 1
for i in range(n):
    d = int(s[i:])
    u[d%p] += 1

res = 0
for v in u.values():
    res += v*(v-1)//2

print(res)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit(0)

val = int(S)
order = 10 ** N
suf_nums = [-1] * N
s = -1
for i in range(N):
    if s != -1:
        val -= s * order
    suf_nums[i] = val
    s = int(S[i])
    order //= 10

surpluses = [0] * P
ans = 0
for num in suf_nums[::-1]:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 0
if P == 2:
    for i, s in enumerate(S, start=1):
        if int(s) % 2 == 0:
            ans += i
elif P == 5:
    for i, s in enumerate(S, start=1):
        if s in "05":
            ans += i
else:
    T = [0] * (N+1)
    d = 0
    for i, s in enumerate(S[::-1], start=1):
        s = int(s) * (10 ** d) + T[i - 1]
        T[i] = s % P
        d += 1
    c = Counter(T)
    ans = sum(x * (x - 1) // 2 for x in c.values())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, p = map(int, input().split())
s = input()
x = {0:1}
ans = 0
if p in [2,5]:
  for i in range(n):
    if int(s[i])%p==0:
      ans += i+1
else:
  for i in range(n-1,-1,-1):
    u = int(s[i:])%p
    ans += x.get(u,0)
    x[u] = x.get(u,0) + 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    mod = 0
    for i, _s in enumerate(s[::-1]):
        mod = (10 ** i % p * int(_s) + mod) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    for i, _s in enumerate(s[::-1]):
        cur = _s + cur
        mod = int(cur) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, P = list(map(int, input().split()))
S = [int(c) for c in input().rstrip()]


if P in [2, 5]:
    total = 0
    for i, x in enumerate(S):
        if x % P == 0:
            # If P == 2
            # all substring ending here with last digit even
            # If P == 5
            # all substring ending here with last digit 5 or 0
            total += i + 1
    print(total)
else:
    # Note P is relatively prime with 10

    # If S is '1234'
    # Want suffixes:
    # s[4] = 1234
    # s[3] =  234
    # s[2] =   34
    # s[1] =    4
    # s[0] =    0
    #
    # Then s[j] - s[i] gives the value of the number int(S[-j:-i]) * 10**(N -i)
    # Since P doesn't divide 10, if P divides s[j] - s[i] it also divides the number

    suf = [0]
    power = 1
    for x in reversed(S):
        suf.append(suf[-1] + x * power)
        power *= 10
    if False:
        # Check
        N = len(S)
        for i in range(N):
            for j in range(i + 1, N + 1):
                print(
                    i,
                    j,
                    int("".join(map(str, S[N - j : N - i]))) * (10 ** i),
                    suf[j] - suf[i],
                )
        print(suf)

    # Count number of s[j] - s[i] pairs that are 0 mod P
    total = 0
    counts = Counter()
    for x in suf:
        x = x % P
        total += counts[x]
        counts[x] += 1
    print(total)

Submission status: Time Limit Exceeded

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

if 10%p==0:
    result = 0
    for i in range(n):
        if s[i]%p==0:
            result += n-i
else:
    r = [0 for _ in range(p)]
    r[0] = 1
    t = 0
    ten = 1
    for i in range(n):
        t += (s[i]%p)*ten
        t %= p
        ten *= 10%p
        r[t] += 1
    result = 0
    for i in r:
        result += i*(i-1)//2
print(result)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit()

val = int(S)
order = 10 ** N
suf_nums = [-1] * N
s = -1
for i in range(N):
    if s != -1:
        val -= s * order
    suf_nums[i] = val
    s = int(S[i])
    order //= 10

surpluses = [0] * P
ans = 0
suf_nums.reverse()
for num in suf_nums:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    for i in range(0, N):
        U[int(S[i:N])%P] += 1
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)

Submission status: Time Limit Exceeded

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

if 10%p==0:
    result = 0
    for i in range(n):
        if s[i]%p==0:
            result += n-i
else:
    r = [0 for _ in range(p)]
    r[0] = 1
    t = 0
    ten = 1
    for i in range(n):
        t += (s[i]*ten)%p
        t %= p
        ten *= 10
        r[t] += 1
    result = 0
    for i in r:
        result += i*(i-1)//2
print(result)

Submission status: Time Limit Exceeded

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

if P == 2 or P == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)
    import sys
    sys.exit()

val = int(S)
order = 10 ** N
suf_nums = [-1] * N
s = -1
for i in range(N):
    if s != -1:
        val -= s * order
    suf_nums[i] = val
    s = int(S[i])
    order //= 10

surpluses = [0] * P
ans = 0
for num in suf_nums.__reversed__():
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Time Limit Exceeded

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

if 10%p==0:
    r = 0
    for i in range(1,n+1):
        if s[-i]%p==0:
            r += n-i+1
    print(r)
else:
    for i in range(2, n+1):
        si.append(si[-1]+s[-i]*(10**(i-1)))
    si = [i%p for i in si]
    si_counter = Counter(si).items()
    r = 0
    for num, count in si_counter:
        if count >= 2:
            r += (count*(count-1))//2
        if num == 0:
            r += count
    print(r)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    temp = 0
    for i in range(N):
        temp += 10**i * int(S[N-i-1])
        temp %= P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
counter=0
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    for i in range(N):
        temp=int(S[N-i-1:])%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
s=input()
ans=0
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:
    mod=[0]*p
    for i in range(n+1):
        if s[i:]=="":
            si=0
        else:
            si =int(s[i:])
        ip = int(si)%p 
        mod[ip]+=1
    ans = sum(m*(m-1)//2 for m in mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    for i in range(N):
        temp = int(S[N - i - 1:]) % P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

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

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


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


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


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


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


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

# test()


def to_index(i, p):
    if i == 0:
        return p % P
    return (p - toint(1, i + 1)) * pow(pow(10, i, P), P - 2, P) % P


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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[0]*P
    list_a[0]+=1
    counter=0
    for i in range(N):
        temp=int(S[N-i-1:])%P
        counter+=list_a[temp]
        list_a[temp]+=1
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[0]*P
    list_a[0]+=1
    counter=0
    for i in range(len(S)):
        temp=int(S[N-i-1:])%P
        counter+=list_a[temp]
        list_a[temp]+=1
    print(counter)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[0]
    counter=0
    for i in range(len(S)):
        temp=int(S[N-i-1:])%P
        counter+=list_a.count(temp)
        list_a.append(temp)
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
n,p=map(int,input().split())
S=input()
M={0:1}
ans=0

if p==2 or p==5: #最下位だけで決まるとき
    for i in range(n):
        s=int(S[i])
        if s%p==0:
            ans+=i+1
    
else: #それ以外は末尾に0をつけても割り切れるかが一致する
    for i in range(n):
        s=int(S[(n-1-i):]) #右からi+1桁取り出す
        r=s%p #剰余
        if r in M: #同じ余りどうしで引き算すると割り切れる
            ans+=M[r]
            M[r]+=1
        else: #なかったら追加
            M[r]=1
print(ans)

Submission status: Time Limit Exceeded

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

if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[]
    for i in range(len(S)):
        list_a.append(int(S[i-1:])%P)
    
    list_a.append(0)
    counter=0
    for i in range(len(list_a)-1):
        counter+=list_a[i+1:].count(list_a[i])
    
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,p = l_in()
s = s_in()

from collections import Counter

c = Counter()

ms = []
m = 0

res = 0
if p == 2:
    print(sum(n-i for i, t in enumerate(reversed(s)) if int(t)%2 == 0))
    exit()

if p == 5:
    print(sum(n-i for i, t in enumerate(reversed(s)) if int(t) in [0, 5]))
    exit()


for i, t in enumerate(reversed(s)):
    t = int(t)
    if t == 0:
        t = p
    m += t*(10**i)
    ms.append(m)
    c[m%p] += 1

print(sum(v*(v-1)//2 for k, v in c.items())+c[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
    for l, s in enumerate(S, 1):
        if int(s) % P == 0: ans += l
else:
    counter = {}
    counter[0] = 1
    for i in range(N-1, -1, -1):
        num = int(S[i:]) % P
        ans += counter.setdefault(num, 0)
        counter[num] += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,p = l_in()
s = s_in()

from collections import Counter

c = Counter()

ms = []
m = 0

res = 0
if p == 2:
    for i, t in enumerate(s[::-1]):
        t = int(t)
        if t%2 == 0:
            res += n-i

    print(res)
    exit()

if p == 5:
    for i, t in enumerate(s[::-1]):
        t = int(t)
        if t == 0 or t == 5:
            res += n-i

    print(res)
    exit()


for i, t in enumerate(s[::-1]):
    t = int(t)
    if t == 0:
        t = p
    m += t*(10**i)
    ms.append(m)
    c[m%p] += 1

for m in ms:
    res += c[m%p]-1
print(res//2 + c[0])

Submission status: Time Limit Exceeded

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


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

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

print(solve(U,S))

Submission status: Time Limit Exceeded

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


for i in range(N):
    U[i+1] = (U[i] + S[N-1-i] * (10 ** i)) % P

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

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

print(solve(U,S))

Submission status: Time Limit Exceeded

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


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

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

print(solve(U,S))

Submission status: Time Limit Exceeded

Solution code:
N,P=map(int,input().split())
S=str(input())
a=[]
b=0
c=1
ans=0
for i in range(int(N*(N+1)/2)):
  a.append(int(S[b:c]))
  c=c+1
  if c==len(S)+1:
    b=b+1
    c=b+1
for i in range(int(N*(N+1)/2)):
  if a[i]%P==0:
    ans=ans+1
print(ans)

Submission status: Time Limit Exceeded

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=ans+i+1
  print(ans)
elif p==5:
  ans=0
  for i in range(n):
    if int(s[i])%5==0:
      ans=ans+i+1
  print(ans)
else:
  G=[[0]*p for i in range(2)]
  G[0]=[i for i in range(p)]
  for i in range(p):
    G[1][i]=G[0][i]*10%p
  R=[[0]*p for i in range(3)]
  a=0
  b=1
  c=2
  for i in range(n):
    x=int(s[i])
    for j in range(p):
      y=(G[1][j]+x)%p
      R[a][y]=R[c][j]+R[c][y]-R[b][j]
    R[a][x%p]+=1
    a=b
    b=c
    c=(c+1)%3
  print(R[c][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    for i,v in enumerate(line):
        if i == 0:
            n = int(v[0])
            p = v[1]
        else:
            numbers = list(v[0])
            # print(numbers)

    count = 0
    leng = len(list(p))
    p = int(p)

    numbers_int = [int(i) for i in numbers]

    map_ = dict()
    a = 10 % p
    for i in set(numbers_int):
        c = i% p
        for j in range(n):
            map_[i,j] = c
            c = c *a


    count = 0
    for i in range(n):
        for j in range(i,n):
            tar = numbers_int[i:j+1]
            # print(tar)
            leng = len(tar)
            su = 0 
            for k,v in enumerate(tar):
                su += map_[v,leng - k -1]
                # print(v, leng - k)
                # print(map_[1,1])
            if su % p == 0:
                count += 1
                # print(tar)

    print(count)