Problem:


Score : 600 points

Problem Statement

We have a sequence of k numbers: d_0,d_1,...,d_{k - 1}.

Process the following q queries in order:

The i-th query contains three integers n_i, x_i, and m_i.
Let a_0,a_1,...,a_{n_i - 1} be the following sequence of n_i numbers: \begin{eqnarray} a_j =  \begin{cases}    x_i & ( j = 0 ) \\    a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 < j \leq n_i - 1 )  \end{cases}\end{eqnarray}
Print the number of j~(0 \leq j < n_i - 1) such that (a_j~\textrm{mod}~m_i) < (a_{j + 1}~\textrm{mod}~m_i).

Here (y~\textrm{mod}~z) denotes the remainder of y divided by z, for two integers y and z~(z > 0).

Constraints

All values in input are integers.

1 \leq k, q \leq 5000

0 \leq d_i \leq 10^9

2 \leq n_i \leq 10^9

0 \leq x_i \leq 10^9

2 \leq m_i \leq 10^9

Input

Input is given from Standard Input in the following format:

k q
d_0 d_1 ... d_{k - 1}
n_1 x_1 m_1
n_2 x_2 m_2
:
n_q x_q m_q

Output

Print q lines.

The i-th line should contain the response to the i-th query.

Sample Input 1

3 1
3 1 4
5 3 2

Sample Output 1

1

For the first query, the sequence {a_j} will be 3,6,7,11,14.

(a_0~\textrm{mod}~2) > (a_1~\textrm{mod}~2)

(a_1~\textrm{mod}~2) < (a_2~\textrm{mod}~2)

(a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)

(a_3~\textrm{mod}~2) > (a_4~\textrm{mod}~2)

Thus, the response to this query should be 1.

Sample Input 2

7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12

Sample Output 2

224489796
214285714
559523809



Sample input:
3 1
3 1 4
5 3 2


Sample output:
1

Submission status: Accepted

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split()))
n=[0 for i in range(q)]
x=[0 for i in range(q)]
m=[0 for i in range(q)]
for i in range(0,q):
    n[i],x[i],m[i]=map(int,input().split())
x=[x[i]%m[i] for i in range(0,q)]
S=sum(d)
for i in range(0,q):
    p=[d[j]%m[i] for j in range(0,k)]
    test=0
    subtest=0
    for j in range(0,k):
        if p[j]!=0:
            test+=1
    s=x[i]%m[i]+sum(p)*((n[i]-1)//k)+sum(p[j] for j in range(0,(n[i]-1)%k))
    for j in range(0,(n[i]-1)%k):
        if p[j]!=0:
            subtest+=1
    if s%m[i]==0:
        print(test*((n[i]-1)//k)+subtest-(s//m[i]))
    else:
        print(test*((n[i]-1)//k)+subtest-(s//m[i]))

Submission status: Accepted

Solution code:
K, Q = map(int, input().split())
D = list(map(int, input().split()))
for _ in range(Q):
    n, x, m = map(int, input().split())
    ds = []
    sumd = 0
    r = 0
    for i, d in enumerate(D):
        tmp = -(-(n-1-i)//K)
        ds.append(d%m)
        sumd += (d%m)*tmp
        if d%m == 0:
            r += tmp
#    print(ds, sumd+x, x, r)
    r += (sumd+x)//m - x//m
#    print(r)
    print(n-1-r)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
import copy

k,q=map(int,input().split())
D=list(map(int,input().split()))
nxm=[list(map(int,input().split())) for i in range(q)]

for n,x,m in nxm:
    dlst=[d%m for d in D]
    count0=[(dlst[0]==0 )* 1]

    lst=[dlst[0]]
    for i in range(1,k):
        lst.append(lst[i-1]+dlst[i])
        count0.append(count0[i-1]+1*(dlst[i]==0))

    num2=(n-1)//k * lst[-1] +  x
    a=(n-1)%k-1
    if a>=0:
        num2+=lst[a]
    #print(num2,n%k)
    num1=n-1-((n-1)//k)*count0[-1]-(num2//m-x//m)
    if a>=0:
        num1-=count0[a]
    print(num1)

Submission status: Accepted

Solution code:
K, Q = map(int, input().split())
D = list(map(int, input().split()))
query = []
for i in range(Q):
    query.append(tuple(map(int, input().split())))


for n, x, m in query:
    Dmod = [d % m for d in D]
    equal = (n - 1) // K * sum(d == 0 for d in Dmod) + sum(d == 0 for d in Dmod[:((n - 1) % K)])

    a0 = x
    an = x + sum(Dmod) * ((n - 1) // K) + sum(Dmod[:((n - 1) % K)])
    small = an // m - a0 // m

    ans = (n - 1) - equal - small
    print(ans)

Submission status: Accepted

Solution code:
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    if N <= K + 1:
        A = [0] * N
        A[0] = X % M
        ans = 0
        for i in range(N-1):
            A[i+1] = (A[i] + D[i]) % M
            if A[i+1] > A[i]:
                ans += 1
        print(ans)
        continue
    ans = N - 1
    t = X%M
    for i in range(K):
        d = (D[i]-1) % M + 1
        a = (N-i-2) // K + 1
        t += d * a
    ans -= t // M
    print(ans)

Submission status: Accepted

Solution code:
k,q = map(int, input().split())
d= list(map(int, input().split()))
for _ in range(q):
    n,x,m = map(int, input().split())
    ans=n-1
    dm=[el%m for el in d]
    loop=(n-1)//k
    rem=(n-1)%k
    eqcnt=0
    lscnt=0
    totsum=0
    remsum=0
    for i in range(k):
        totsum+=dm[i]
        if i<rem:
            remsum+=dm[i]
        if dm[i]==0:
            eqcnt+=1
            if i<rem:
                ans-=1
    ans-=eqcnt*loop
    lscnt+=totsum//m*loop+remsum//m
    lscnt+=(totsum%m*loop+remsum%m+x%m)//m
    ans-=lscnt
    print(ans)

Submission status: Accepted

Solution code:
k,q = input().split()
k = int(k)
q = int(q)

d = input().split()
for i in range(k):
    d[i] = int(d[i]) - 1

import numpy as np
d = np.array(d)

for r in range(q):
    n,x,m = input().split()
    n = int(n)
    x = int(x)
    m = int(m)

    dd = d % m + np.ones(k,dtype="int")
    DD = np.concatenate((np.zeros(1, dtype="int"),np.cumsum(dd) ))
    
    alast = x + DD[k]*((n-1)//k) + DD[(n-1)%k]
    kuriagari = alast // m - x//m

#    print([x%m, alast, alast%m, n - kuriagari - 1])
    print (n - 1 - kuriagari)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans


'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''


#a = list(map(int, input().split()))

k, q = list(map(int, input().split()))
d = list(map(int, input().split()))

que = []
for i in range(q):
    que.append(list(map(int, input().split())))
    
#print(que)

dsum = [0]

for i in range(k):
    dsum.append(dsum[-1]+d[i])

    
for i in range(q):
    dr = [d[j]%que[i][2] for j in range(len(d))]
    #print(dr)
    drsum = [0 for i in range(k+1)]
    for j in range(k):
        drsum[j+1] = drsum[j] + dr[j]
    count0 = [0 for i in range(k+1)]
    for j in range(k):
        if(dr[j]==0):
            count0[j+1] = count0[j]+1
        else:
            count0[j+1] = count0[j]
            
    times = (que[i][0]-1) // k
    amari = (que[i][0]-1) % k
    
    #print(drsum)
    #print(count0)
    #print(times,amari)
    
    total = que[i][1] + drsum[-1]*times + drsum[amari]
    num0 = count0[-1]*times + count0[amari]
    #print("num0",num0)
    ans = total//que[i][2] - que[i][1]//que[i][2]
    ans = que[i][0] - ans - num0 - 1
    
    print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

K, Q = na()
d = na()

for z in range(Q):
    n, x, m = na()

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1

    lpre = 0
    turn = 0
    # print(d[rem:] +  d[:rem])
    j = rem
    for i in range(K):
        cur = (lpre + d[j]) % m
        if lpre < cur:
            turn += 1
        lpre = cur
        j += 1
        if j == K:
            j = 0
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

k,q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n,x,mod = map(int, input().split())
    dd = [di%mod if di%mod else mod for di in d]
    a,b = divmod(n-1, k)
    tmp = x%mod + a*sum(dd) + sum(dd[:b])
    print(n-1-tmp//mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

k, q = [int(item) for item in input().split()]
d = [int(item) for item in input().split()]
nxm = []
for _ in range(q):
    n, x, m = [int(item) for item in input().split()]
    nxm.append((n, x, m))

for n, x, m in nxm:
    n -= 1
    newd = []
    is_zero = []
    sum_newd = 0
    for item in d:
        sum_newd += item % m
        newd.append(item % m)
        is_zero.append(item % m == 0)
    loop = n // k
    rest = n % k
    total = loop * (sum_newd) + (x % m) 
    zeros = loop * sum(is_zero)
    total += sum(newd[:rest])
    zeros += sum(is_zero[:rest])
    rollover = total // m
    ret = n - rollover - zeros
    print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
k, q = map(int,input().split())
D = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
    n = A[i][0]
    x = A[i][1]
    m = A[i][2]
    ans = 0
    B = [x%m]
    BP = [0] * (k+1)
    n -= 1
    for j in range(k):
        B.append((B[-1] + D[j]) % m)
    ans0 = 0
    for j in range(len(B)-1):
        if B[j+1] > B[j]:
            BP[j+1] = 1
            ans0 += 1
    # print(B,BP)
    if B[-1] != B[0]:
        if B[-1] > B[0]:
            ans1 = [ans0-1, ans0]
        elif B[-1] < B[0]:
            # print("sage")
            ans1 = [ans0, ans0+1]
        d = (B[-1] - B[0]) % m
        kn = n // k
        c = (B[0] + d * kn) % m
        sag = (B[0] + d * kn) // m
        # print(((B[0] + d * kn) - c) % m,"zero")
        ans = ans1[0] * sag + ans1[1] * (kn-sag)
        # print("kn",kn,"sag",sag,"c",c)
        for ii in range(n%k):
            cm = c
            # print("plus")
            c += D[ii]
            if c >= m:
                c %= m
            
            if c>cm:
                ans += 1    
        print(ans)
        
    else:
        # print("eq")
        print(ans0 * (n//k) + sum(BP[:n%k+1]))

Submission status: Accepted

Solution code:
import numpy as np

k, q = map(int, input().split())
d = np.array(list(map(int, input().split())))

for i in range(q):
  n, x, m = map(int, input().split())
  mod_d = d % m
  modsum_d = mod_d.cumsum()
  _q, _m = divmod(n - 1, k)
  
  ans = modsum_d[k - 1] * _q
  if _m > 0:
    ans += modsum_d[_m - 1]
  ans = n - 1 - (ans + x % m) // m - np.count_nonzero(mod_d == 0) * _q
  if _m > 0:
    ans -= np.count_nonzero(mod_d[0 : _m] == 0)
  print(ans)

Submission status: Accepted

Solution code:
k, q = list(map(int, input().split()))
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for _ in range(q)]

D = [[0] * 2 for _ in range(k)]
for i in range(q):
  n, x, m = nxm[i]
  D[-1] = [0, 0]
  D[0][0] = d[0] % m
  D[0][1] = 0

  for j in range(k):
    D[j][0] = (D[j - 1][0] + d[j] % m)
    D[j][1] = D[j - 1][1]
    if D[j - 1][0] != D[j][0]:
      D[j][1] += 1

  N, M = divmod(n - 1, k)

  ans = N * D[-1][1]
  t = N * D[-1][0] + (x % m)
  ans -= t // m
  t = t % m
  if M != 0:
    ans += D[M - 1][1]
    t += D[M - 1][0]
    ans -= t // m
  
  print(ans)

Submission status: Accepted

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split()))

def solve(n,x,m):
    S=[0]*(k+1)
    cnt_z=[0]*(k+1)
    for i in range(k):
        a=d[i]%m
        S[i+1]=S[i]+a
        cnt_z[i+1]=cnt_z[i]
        if a==0:
            cnt_z[i+1]+=1
    pp=(n-1)//k#商
    r=(n-1)%k#余り
    
    s=x+S[-1]*pp+S[r]
    
    ans=(n-1)-s//m-cnt_z[-1]*pp-cnt_z[r]
    print(ans)
    
    


for i in range(q):
    n,x,m=map(int,input().split())
    x%=m
    solve(n,x,m)

Submission status: Accepted

Solution code:
def process(k, d, n, x, m):
  d_mod = [di % m for di in d]
  sum_d_mod = sum(d_mod)
  inc_times1 = len([d_mod_i for d_mod_i in d_mod if d_mod_i])
  rem_d_mod = sum(d_mod[0:(n-1)%k])
  inc_times2 = len([d_mod_i for d_mod_i in d_mod[0:(n-1)%k] if d_mod_i])
  last = x + sum_d_mod * ((n-1) // k) + rem_d_mod
  first = x
  ans = inc_times1 * ((n-1) // k) + inc_times2
  ans -= last // m - first // m
  print(ans)


def main():
  k, q = map(int, input().split())
  d = list(map(int, input().split())) 
  for i in range(q):
    n, x, m = map(int, input().split())
    process(k, d, n, x, m)



if __name__ == "__main__" :
  main()

Submission status: Accepted

Solution code:
k,q = map(int,input().split())
d = list(map(int,input().split()))
al = []
for i in range(q):
    n,x,m = map(int,input().split())
    pd = []
    count = 0
    for j in range(k):
        pd.append(d[j]%m)
        if d[j]%m == 0:
            count += 1
    a = sum(pd)
    ans = x%m
    ans += a*((n-1)//k)
    #print(pd)
    c = 0
    for j in range((n-1)%k):
        ans += pd[j]
        if pd[j] == 0:
            c += 1
    al.append(n-1-(ans//m)-count*((n-1)//k)-c)
for i in range(q):
    print(al[i])

Submission status: Accepted

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

def main():
    k,q=map(int,input().split())
    D=tuple(map(int,input().split()))
    for _ in range(q):
        n,x,m=map(int,input().split())
        x%=m
        Di=[]
        zero=0
        for d in D:
            tmp=d%m
            if tmp==0:
                zero+=1
            Di.append(tmp)
        s=sum(Di)
        cycles=(n-1)//k
        cycle_sum=cycles*s
        remain=(n-1)%k
        #print(remain)
        last=x+cycle_sum
        for i in range(remain):
            last+=Di[i]
        #print(last)
        q=n-1
        q-=zero*cycles
        for i in range(remain):
            if Di[i]==0:
                q-=1
        q-=last//m
        print(q)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

K, Q = map(int, readline().split())

D = list(map(int, readline().split()))

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    x%= mod
    D2 = [d%mod for d in D]
    res = 0
    cnt = 0
    zero = 0
    for d2 in D2:
        res += d2
        if res > mod:
            cnt += 1
            res -= mod
        if not d2:
            zero += 1
    
    loop =  ((n-1)//K)
    minus = loop*cnt
    zero *= loop
    res2 = 0
    for i in range((n-1)%K):
        res2 += D2[i]
        if not D2[i]:
            zero += 1
        if res2 > mod:
            res2 -= mod
            minus += 1
    minus += (x%mod + loop*res + res2)//mod
    Ans[q] = n-1 - zero - minus
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
k,q = map(int,input().split())
d = list(map(int,input().split()))

def query(n,x,m):
    res = n-1
    n -= 1
    x %= m
    s1 = 0
    t1 = 0
    for i in range(k):
        s1 += d[i]%m
        if d[i]%m==0:
            t1 += 1
    s2 = 0
    t2 = 0
    for i in range(n%k):
        s2 += d[i]%m
        if d[i]%m==0:
            t2 += 1
    x += s1*(n//k)+s2
    res -= x//m
    res -= t1*(n//k)+t2
    return res

for i in range(q):
    n,x,m = map(int,input().split())
    print(query(n,x,m))

Submission status: Accepted

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

K, Q = map(int, readline().split())

D = list(map(int, readline().split()))

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    x%= mod
    D2 = [d%mod for d in D]
    res = 0
    cnt = 0
    zero = 0
    for d2 in D2:
        res += d2
        if res > mod:
            cnt += 1
            res -= mod
        if not d2:
            zero += 1
    
    loop =  ((n-1)//K)
    minus = loop*cnt
    zero *= loop
    res2 = 0
    for i in range((n-1)%K):
        res2 += D2[i]
        if not D2[i]:
            zero += 1
        if res > mod:
            res -= mod
            minus += 1
    minus += (x%mod + loop*res + res2)//mod
    Ans[q] = n-1 - zero - minus
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
k,q = map(int,input().split())
d = list(map(int,input().split()))
for _ in range(q):
  n,x,m = map(int,input().split())
  x %= m
  dm = []
  for dx in d:
    dm.append((dx-1)%m+1)
  sumd = (n-1)//k * sum(dm) + sum(dm[:(n-1)%k])
  ans = n - 1 - (x+sumd)//m + (x)//m
  #print(n , 1 , (x+sumd)//m , (x)//m)
  #print(sumd)
  #print(dm)
  print(ans)

Submission status: Accepted

Solution code:
K, Q = map(int, input("").split())
d_ = list(map(int, input("").split()))
for _ in range(Q):
    n,x,m = map(int, input("").split())
    d = [0]*K;zeroes = [0]*(K+1);sum = [0]*(K+1)
    for i in range(K):d[i] = d_[i] % m
    for i in range(K):zeroes[i+1] = zeroes[i] + (d[i] == 0)
    for i in range(K):sum[i+1] = sum[i] + d[i]
    #print(zeroes, sum)  
    s = (n-1)//K*sum[K] + sum[(n-1)%K]
    s += x%m
    #print(s)
    num0 = (n-1)//K*zeroes[K] + zeroes[(n-1)%K]
    print(n-1-s//m-num0)

Submission status: Accepted

Solution code:
k, q = map(int, input().split())
d = list(map(int, input().split()))
for _ in range(q):
    n, x, m = map(int, input().split())
    cum = [0]*(k+1)
    cnt = [0]*(k+1)
    for i in range(k):
        cum[i] = cum[i-1]+d[i]%m
        cnt[i] = cnt[i-1]
        if d[i]%m == 0:
            cnt[i]+=1
    res = x%m+cum[k-1]*((n-1)//k)+cum[(n-1)%k-1]
    s = res//m
    print(n-1-s-cnt[k-1]*((n-1)//k)-cnt[(n-1)%k-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# %%
import numpy as np
# %%
stdin = open(0)

# %%
K, Q = map(int, stdin.readline().split())
D = np.array(stdin.readline().split(), np.int64)
m = map(int, stdin.read().split())
query = tuple(zip(m, m, m))


# %%
def solve(n, x, m):
    Dm = D % m
    Dcum = np.cumsum(Dm)
    q, r = divmod(n - 1, K)
    last = x + Dcum[-1] * q
    if r:
        last += Dcum[r - 1]
    is_zero = np.cumsum(Dm == 0).astype(np.int64)
    stable = is_zero[-1] * q
    if r:
        stable += is_zero[r - 1]
    decr = (last // m) - (x // m)
    return n - 1 - stable - decr


# %%
for n, x, m in query:
    print(solve(n, x, m))

# %%

Submission status: Runtime Error

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split()))
nxm=[list(map(int,input().split())) for _ in [0]*q]
for n,x,m in nxm:
  l=[0]*n
  l[0]=x%m
  for i in range(0,n-1):
    l[i+1]=l[i]+d[i%k]
    l[i+1]%=m
  ans=0
  for j in range(0,n-1):
    if l[j+1]>l[j]:
      ans+=1
  print(ans)

Submission status: Runtime Error

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split))
for _ in range(q):
  n,x,m=map(int,input().split())
  l=[0]*n
  l[0]=x%m
  for i in range(n):
    l[i+1]=l[i]+d[i%k]
    l[i+1]%=m
  ans=0
  for j in range(n):
    if l[j+1]>l[i]:
      ans+=1
  print(ans)

Submission status: Runtime Error

Solution code:

import numpy as np
def resolve():
    K, Q = map(int, input().split())
    D = np.array(input().split(), dtype=np.int64)


    for _ in range(Q):
        n, x, m = map(int, input().split())
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero = [int(e == 0) for e in E]
        zero_acc = np.cumsum(zero)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    
import numpy as np
def resolve():
    K, Q = map(int, input().split())
    D = np.array(input().split(), dtype=np.int64)


    for _ in range(Q):
        n, x, m = map(int, input().split())
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero = [int(e == 0) for e in E]
        zero_acc = np.cumsum(zero)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=list(map(int,readline().split()))
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.array([0]+tmpD,dtype=np.int64)
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=tmpD.count(0)*(n//k)
    count+=tmpD[:n%k].count(0)
    ans=n-x//m-count
    print(ans)

Submission status: Runtime Error

Solution code:
k,q = map(int,input().split())
d = list(map(int,input().split()))

for _ in range(q):
  n,x,m = map(int,input().split())
  dm = [a%m for a in d]
  q,r = divmod(n-1,len(dm))
  cumsum = dm[0]+ [dm[i]+dm[i-1] for i in range(1,k)]
  
  zero = q*dm.count(0) + dm[:r].count(0)
  
  alast = x + q*cumsum[-1] + cumsum[r-1]
  minus = alast//m - x//m
  
  print(n-1 - zero - minus)

Submission status: Runtime Error

Solution code:
import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), dtype=np.int)
for _ in range(q):
  n, x, m = map(int, input().split())
  quot = (n-1) // k
  rest = (n-1) % k
  dmod = d % m
  same = (k - dmod.count_nonzero()) * quot + rest - dmod[:rest].count_nonzero()
  a_last = x % m + dmod.sum() * quot + dmod[:rest].sum()
  beyond = a_last // m
  print(n - 1 - same - beyond)

Submission status: Runtime Error

Solution code:
k,q = map(int,input().split())
d = list(map(int,input().split()))
n = [0]*q
x = n.copy()
m = n.copy()
for i in range(q):
    n[i],x[i],m[i] = map(int,input().split())
    
for i in range(q):
    a = [x[i]%m[i]]*n[i]
    count = 0
    for j in range(n[i]-1):
        a[j+1] = (a[j] + d[j%k])%m[i]
        if a[j+1] > a[j]:
            count+=1
    print(count)

Submission status: Runtime Error

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

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list(map(lambda x:x%m,d))
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k):
        if e[i] == 0:
            zero += 1
    s = sum(e)*((n-1)//k)
    for i in range((n-1)%k):
        s += e[i]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

Submission status: Runtime Error

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

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list(map(lambda x:x%m,d))
    zero = 0
    for i in range(k):
        if e[i] == 0:
            zero += 1
    zero = zero*((n-1)//k)
    for i in range((n-1)%k):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

Submission status: Runtime Error

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

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = [i%m for i in d]
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

Submission status: Runtime Error

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

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list(map(lambda x:x%m,d))
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

Submission status: Runtime Error

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

import sys
import math
import numpy as np
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list(map(lambda x:x%m,d))
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k+1):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k) + f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

Submission status: Runtime Error

Solution code:
,q = map(int, input().split())
d = list(map(int, input().split()))

def query(n,x,m):
  x %= m
  ans = n-1
  n -= 1
  s1 = 0
  t1 = 0
  for i in range(k):
    s1 += d[i] % m
    if d[i] % m == 0:
      t1 += 1
  s2 = 0
  t2 = 0
  for i in range(n%k):
    s2 += d[i] % m
    if d[i] % m == 0:
      t2 += 1
  x += s1 * (n//k) + s2
  ans -= x//m
  ans -= t1 * (n//k) + t2
  
  print(ans)
  
    

for _ in range(q):
  n,x,m = map(int, input().split())
  query(n,x,m)

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	k,q = MI()
	d = LI()
	d = np.array(d)
	ans = [0]*q
	for i in range(q):
		n,x,m = MI()
		d_modm = d%m
		zero = (n//k)*np.sum(d_modm==0) + np.sum((d_modm==0)[:n%k-1])
		lst = x + (n//k)*np.sum(d_modm) + np.sum((d_modm)[:n%k-1])
		ans[i]=n-1-zero-(lst//m-x//m)
	printV(ans)
if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	k,q = MI()
	d = LI()
	d = np.array(d)
	for _ in range(q):
		n,x,m = MI()
		d_modm = d%m
		zero = (n//k)*np.sum(d_modm==0) + np.sum((d_modm==0)[:n%k-1])
		lst = x + (n//k)*np.sum(d_modm) + np.sum((d_modm)[:n%k-1])
		print(n-1-zero-(lst//m-x//m))
if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    query = [list(map(int, input().split())) for i in range(q)]
    for n, x, m in query:
        print(answer_query(n, x, m))

def answer_query(n, x, m):
    l = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = sum(l)*((n-1)//k)
    total += x%m
    zero_total = zero*((n-1)//k)

    s = n
    n -= 1
    n -= n//k * k
    t = 0
    for i in range(n):
        t += l[i]
    total += t

    for i in range(n):
        if l[i] == 0:
            zero_total += 1

    return s-1-total//m-zero_total

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [list(map(int, input().split())) for i in range(q)]
ans = []
for n, x, m in query:
    l = [d[i]%m for i in range(k)]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    total = sum(l)*count + x%m
    rem = n % k
    total += sum(l[:rem])
    zero_total += l[:rem].count(0)
    ans.append(n-total//m-zero_total)
print("\n".join(ans))