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: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        smd = 0
        md0 = 0
        a = (n - 1) % K
        for i in range(K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
            if i == a - 1:
                smda = smd
                mda0 = md0
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    zero = sum(e == 0 for e in eee)
    acc = list(accumulate(eee))
    loop, rem = divmod(n - 1, k)
    tot = x % m + acc[-1] * loop
    if rem > 0:
        tot += acc[rem - 1]
    dame = tot // m
    # print(n, x, m)
    # print(eee)
    # print(acc)
    # print(loop, rem)
    # print(tot, dame)
    return n - 1 - dame - zero * loop


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))

Submission status: Wrong Answer

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:
    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) + sum(newd[:rest-1]) 
    zeros = loop * sum(is_zero) + sum(is_zero[:rest-1])
    rollover = total // m
    ret = n - 1 - rollover - zeros
    print(ret)

Submission status: Wrong Answer

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 - (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: Wrong Answer

Solution code:
def main():
    from collections import defaultdict

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

        u = v = x % m
        cnt = 0

        d = defaultdict(bool)
        ctr = defaultdict(int)
        es = [d % m for d in ds]
        for i in range(n - 1):
            j = i % k
            u = (u + es[j]) % m
            if d[u, j]:
                cnt = cnt * (n - 1) // i + ctr[((n - 1) % i) - 1]
                break
            d[u, j] = True

            if u > v:
                cnt += 1

            ctr[i] = cnt
            v = u

        print(cnt)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

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

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

  for j in range(k):
    D[j] = [(D[j - 1][0] + d[j] % m), 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
  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: Wrong Answer

Solution code:
#TLE
k,q=map(int,input().split())
dd=list(map(int,input().split()))
def calc(a,b,m,c,mod):
  #(a,b),(a+m,b+m),(a+2m,b+2m)...(a+cm,b+cm)
  #これらのうち、modをとってa+km<b+kmのもの
  #O(1)またはO(logなにか)
  ans=0
  for i in range(c+1):
    if (a+i*m)%mod<(b+i*m)%mod:ans+=1
  return ans
for _ in range(q):
  n,x,mod=map(int,input().split())
  if n>=1000:exit()
  v=[x%mod]
  d=[]
  for i in range(k):
    if i!=0:d.append((d[i-1]+dd[i])%mod)
    else:d.append(dd[0])
    v.append((v[0]+d[i])%mod)
  if n<=k+1:
    ans=0
    for i in range(1,n):
      if v[i-1]<v[i]:ans+=1
    print(ans)
    break
  ans=0
  if v[0]<v[1]:ans=1
  v=v[1:]
  n-=1
  m=d[-1]
  z=[]
  for i in range(k-1):
    c=n//k-1
    if i+1<n%k:c+=1
    z.append(c)
    ans+=calc(v[i],v[i+1],m,c,mod)
  #print(d)
  #print(v)
  #print(z)
  print(ans)

Submission status: Wrong Answer

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-2)%k])
  inc_times2 = len([d_mod_i for d_mod_i in d_mod[0:(n-2)%k] if d_mod_i])
  last = x + sum_d_mod * ((n-2) // k) + rem_d_mod
  first = x
  ans = inc_times1 * ((n-2) // 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: Wrong Answer

Solution code:
#>=はmの倍数をまたいだ回数
k,q = map(int, input().split( ))
d = list(map(int, input().split( )))
from collections import Counter
for i in range(q):
    n,x,m=map(int, input().split( ))
    d2 = [di%m for di in d if di%m]
    #j = Counter(d)[0]
    sm = x%m+sum(d2)*(n//k)+sum(d2[:n%k])
    #print(n-1-sm//m-j*(n//k)-Counter(d2[:n%k])[0])
    print(len(d2)*((n-1)//k) -sm//m -Counter(d2[:n%k])[0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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


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

    D2=[d%m for d in  D]
    S=sum(D2)
    D0=D2.count(0)
    ANS=n//k*(k-D0) - ((n//k*S)+(x%m))//m 

    x2=(x+S*(n//k))%m

    for i in range(n-n//k*k-1):
        nx=(x2+D[i])%m

        if nx>x2:
            ANS+=1
        x2=nx

    print(ANS)

Submission status: Wrong Answer

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
    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: Wrong Answer

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]
    s = (n-1)//K*sum[K] + sum[(n-1)%K]
    s += x
    num0 = (n-1)//K*zeroes[K] + zeroes[(n-1)%K]
    print(n-1-s//m-num0)

Submission status: Wrong Answer

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)
    cnt = [0]*(k)
    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//k)+cum[(n-1)%k]
    s = res//m
    print(n-1-s-cnt[-1]*(n//k)-cnt[(n-1)%k])

Submission status: Time Limit Exceeded

Solution code:
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:
    prev = x
    ans = 0
    cur = 0
    for i in range(k):
        prev += (d[i] % m) * ((n + k - i  - 2) // k)
        if d[i] % m == 0:
            cur += ((n + k - i  - 2) // k)
    print(n - prev // m + x // m - cur - 1)

Submission status: Time Limit Exceeded

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__":
    resolve()

Submission status: Time Limit Exceeded

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

from itertools import accumulate
def resolve():
    K, Q = map(int, inp().split())
    D = list(map(int, inp().split()))

    for _ in range(Q):
        n, x, m = map(int, inp().split())
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = [d%m for d in D]
        acc_E = list(accumulate(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 = list(accumulate(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: Time Limit Exceeded

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

for _ in range(q):
  n,x,m=map(int,input().split())
  alist=[x]
  for i in range(n-1):
    alist.append(alist[-1]+dlist[i%k])
    
  #print(alist)
  answer=0
  for i in range(1,n):
    if alist[i-1]%m<alist[i]%m:
      answer+=1
      
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import math

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

    loop_k = range(k)
    for query in [0]*q:
        n, x, m = map(int, input().split())
        last = x
        count_equal = 0
        for i in loop_k:
            count_di = math.ceil((n-1-i) / k)
            last += (d[i] % m) * count_di
            if d[i] % m == 0:
                count_equal += count_di
        # 全体から > と = の個数を引く → < の数が求まる
        print((n-1) - (last//m - x//m) - count_equal)

        
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        kmod = (n-1)%k
        kdiv = (n-1)//k
        dmodmCounter = collections.Counter(dmodm)
        dmodmkCounter = collections.Counter(dmodm[:kmod])
        dmodcum = list(itertools.accumulate(dmodm))
        p0 = dmodmCounter[0] * kdiv + dmodmkCounter[0]
        an = x + (kmod != 0) * dmodcum[kmod-1] + dmodcum.pop() * kdiv
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        kmod = (n-1)%k
        kdiv = (n-1)//k
        dmodmCounter = collections.Counter(dmodm)
        dmodmkCounter = collections.Counter(dmodm[:(kmod)])
        dmodcum = [0] + list(itertools.accumulate(dmodm))
        p0 = dmodmCounter[0] * (kdiv) + dmodmkCounter[0]
        an = x + dmodcum[kmod] + dmodcum.pop() * (kdiv) 
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        dmodmCounter = collections.Counter(dmodm)
        dmodmkCounter = collections.Counter(dmodm[:((n-1)%k)])
        dmodcum = [0] + list(itertools.accumulate(dmodm))
        p0 = dmodmCounter[0] * ((n-1)//k) + dmodmkCounter[0]
        an = x + dmodcum[-1] * ((n-1)//k) + dmodcum[(n-1)%k]
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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=list(map(lambda x:x%m,D))
    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: Time Limit Exceeded

Solution code:
import sys
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=list(map(lambda x:x%m,D))
    SD=[0]+tmpD
    n-=1
    for i in range(1,k):
        SD[i+1]+=SD[i]
    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: Time Limit Exceeded

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())
    tmpD=list(map(lambda x:x%m,D))
    SD=[0]+tmpD
    n-=1
    for i in range(1,k):
        SD[i+1]+=SD[i]
    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: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    k, q = map(int, input().split())
    d = np.array(list(map(int, input().split())), dtype=np.int64)
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum((d[:(n-2) % k+1]-1) % m+1)
        d3 = sum((d[(n-2) % k+1:]-1) % m+1)
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    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:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        d2 = [(i-1) % m+1 for i in d]
        print(n-1-(x % m+sum(d2)*((n-2)//k)+sum(d2[:(n-2) % k+1]))//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    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:
        d2 = [(i-1) % m+1 for i in d]
        print(n-1-(x % m+sum(d2)*((n-2)//k)+sum(d2[:(n-2) % k+1]))//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    import numpy as np
    input = stdin.readline
    k, q = map(int, input().split())
    d = np.array(list(map(int, input().split())), dtype=np.int64)
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = (d-1) % m+1
        print(n-1-(x % m+sum(d2)*((n-2)//k)+sum(d2[:(n-2) % k+1]))//m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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:
        d2 = [(i-1) % m+1 for i in d]
        print(n-1-(x % m+sum(d2)*((n-2)//k)+sum(d2[:(n-2) % k+1]))//m)


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d, d0 = [], []
        pre_d = d[0] % m
        pre_d0 = int(d[0] % m == 0)
        _d.append(pre_d)
        d0.append(pre_d0)
        for val in d[1:]:
            pre_d += val % m
            pre_d0 += int(val % m == 0)
            _d.append(pre_d)
            d0.append(pre_d0)


        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[n_rest - 1]
            d0_rest = d0[n_rest - 1]

        a_last = x + n_d * _d[-1] + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0[-1] + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [d[0] % m]
        d0 = [int(d[0] % m == 0)]
        for val in d[1:]:
            _d.append(_d[-1] + val % m)
            d0.append(d0[-1] + int(val % m == 0))


        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[n_rest - 1]
            d0_rest = d0[n_rest - 1]

        a_last = x + n_d * _d[-1] + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0[-1] + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [val % m for val in d]

        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = sum(_d[:n_rest])
            d0_rest = _d[:n_rest].count(0)

        a_last = x + n_d * sum(_d) + _d_rest
        n_step = a_last // m
        # n_same

        n_same = n_d * _d.count(0) + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [val % m for val in d]

        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest = 0 if n_rest == 0 else sum(_d[:n_rest])
        a_last = x + n_d * sum(_d) + _d_rest
        n_step = a_last // m
        # n_same
        d0_rest = 0 if n_rest == 0 else _d[:n_rest].count(0)
        n_same = n_d * _d.count(0) + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [d[0] % m]
        for val in d[1:]:
            _d.append(_d[-1] + val % m)

        # n_step
        n_d = (n-1)// k
        n_rest = (n-1) % k
        x %= m
        _d_rest = 0 if n_rest == 0 else _d[n_rest-1]
        a_last = x + n_d * _d[k-1] + _d_rest
        n_step = a_last // m - x // m
        # n_same
        d0 = [1] if _d[0] == 0 else [0]
        for val in d[1:]:
            plus = 1 if val % m == 0 else 0
            d0.append(d0[-1] + plus)
        d0_rest = 0 if n_rest == 0 else d0[n_rest-1]
        n_same = n_d * d0[k-1] + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

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


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())
        last = x
        eq = 0
        for j in range(k):
            num = math.ceil((n-1-j)/k)
            last += (d[j] % m)*num
            if d[j] % m == 0:
                eq += num
        ans = (n-1) - (last//m - x//m) - eq
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  k, q = map(int, input().split())
  d = tuple(map(int, input().split()))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = []
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(d_mod[:rem])
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  k, q = map(int, input().split())
  d = tuple(map(int, input().split()))
  from collections import deque
  from itertools import islice
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = deque()
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(islice(d_mod, 0, rem))
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  k, q = map(int, input().split())
  d = list(map(int, input().split()))
  from collections import deque
  from itertools import islice
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = deque()
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(islice(d_mod, 0, rem))
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  k, q = map(int, input().split())
  d = list(map(int, input().split()))
  from collections import deque
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = deque()
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    d_mod = list(d_mod)
    rem_sum = sum(d_mod[:rem])
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
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())
    x %= m
    d_mod = []
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(d_mod[:rem])
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
k, q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
  n, x, m = map(int, input().split())
  x %= m
  d_mod = []
  for i in d:
    i_mod = i % m
    if i_mod == 0:
      d_mod.append(m)
    else:
      d_mod.append(i_mod)
  d_mod_sum = sum(d_mod)
  rep = (n-1) // k
  rem = (n-1) % k
  rem_sum = sum(d_mod[:rem])
  ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
k,q = list(map(int,input().split(" ")))
d  = list(map(int,input().split(" ")))
nxm = []
for i in range(q):
    nxm.append(list(map(int,input().split(" "))))
for n,x,m in nxm:
    a = (n - 1) // k
    b = 0
    f = 0
    for i in range(k):
        b += d[i]%m
        if(d[i]%m == 0):
            f += 1
    c = 0
    e = 0
    for i in range((n-1)%k):
        c += d[i]%m
        if(d[i]%m == 0):
            e += 1
    ret = (x%m + a*b + c)//m + a*f + e
    print(n - ret - 1)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    k,q = LI()
    d = LI()
    aa = [LI() for _ in range(q)]

    def f(n,x,m):
        e = [c%m for c in d]
        n -= 1
        s = sum(e)
        t = s * (n//k) + sum(e[:n%k])
        xt = x + t
        z = [1 if c == 0 else 0 for c in e]
        zs = sum(z) * (n//k) + sum(z[:n%k])
        # print(xt, x, m, zs,n%k)
        return n - (xt//m - x//m) - zs

    r = [f(n,x,m) for n,x,m in aa]
    return JA(r, "\n")


print(main())