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

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

for n, x, m in queries:
    d_mod = [elem % m for elem in d]
    rem_d_mod = d_mod[: (n - 1) % k]
    print(n - 1 - (x % m + ((n - 1) // k) * sum(d_mod) + sum(rem_d_mod)) // m
          - ((n - 1) // k) * d_mod.count(0) - rem_d_mod.count(0))

Submission status: Time Limit Exceeded

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

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


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)

Submission status: Time Limit Exceeded

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

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


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    # a_j mod m = a_{j+ 1} mod m
    for i in range(k):
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)

Submission status: Time Limit Exceeded

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


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    # a_j mod m = a_{j+ 1} mod m
    for i in range(k):
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Mar  3 00:54:29 2020

@author: Kanaru Sato
"""

def Q(n,x,m,k,*d):
    a = []
    a.append(x)
    for h in range(1,n):
        dindex = (h-1)%k
        a.append(a[h-1]+d[0][dindex])
    count = 0
    for h in range(0,n-1):
        if a[h]%m < a[h+1]%m:
            count += 1
    return count

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


J = []

for j in range(0,q):
    n = ints[j][0]
    x = ints[j][1]
    m = ints[j][2]
    res = Q(n,x,m,k,D)
    J.append(res)

[print(J[i]) for i in range(0,q)]

Submission status: Time Limit Exceeded

Solution code:
stdin = open(0)
k, q = map(int, stdin.readline().split())
d = [int(x) for x in stdin.readline().split()]

for _ in range(q):
    n, x, m = map(int, stdin.readline().split())
    z = 0
    last = x
    ans = 0
    
    for i in range(k):
        dnum = (n-1-i+(k-1))//k
        last += d[i]%m * dnum
        if d[i]%m == 0:
            z += dnum
        
    ans = (n-1) - (last//m - x//m) - z
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.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())
    d = [di%m for di in d_]
    ans = n-1
    
    s, a = divmod(n-1, k)
    ans -= s*d.count(0)
    
    for i in range(a):
        if d[i]==0:
            ans -= 1
            
    last = x+s*sum(d)
    
    for i in range(a):
        last += d[i]
    
    ans -= last//m-x//m
    
    print(ans)

Submission status: Time Limit Exceeded

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

import sys

debug = False

def solve(ds, n, x, m):
    ds = [d % m for d in ds]

    nr_loop = (n - 1) // len(ds)
    lastloop_remaining = (n - 1) % len(ds)
    a_n = x
    cnt_zero = 0
    for i in range(0, len(ds)):
        dmod = ds[i] % m
        a_n += (dmod) * nr_loop
        if dmod == 0:
            cnt_zero += nr_loop
        if i < lastloop_remaining:
            a_n += dmod
            if dmod == 0:
                cnt_zero += 1
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_zero


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
k, q = map(int, input().split())
d = [int(x) for x in input().split()]

for _ in range(q):
    n, x, m = map(int, input().split())
    z = 0
    last = x
    ans = 0

    for i in range(k):
        dnum = (n-1-i+(k-1))//k
        last += d[i]%m * dnum
        if d[i]%m == 0:
            z += dnum
        
    ans = (n-1) - (last//m - x//m) - z
    print(ans)

Submission status: Time Limit Exceeded

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

import sys

debug = False

def solve(ds, n, x, m):
    cnt_zero_in_d = 0
    ds_m = []
    for d in ds:
        ds_m.append(d % m)
        if ds_m[-1] == 0:
            cnt_zero_in_d += 1
    ds = [d % m for d in ds]
    a_n = x + sum(ds[0:(n - 1) % len(ds)]) + ((n - 1) // len(ds) * sum(ds)) 
    cnt_same = ds[0:(n - 1) % len(ds)].count(0) + ((n - 1) // len(ds) * cnt_zero_in_d)
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_same


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

debug = False

def solve(ds, n, x, m):
    ds = [d % m for d in ds]
    a_n = x + sum(ds[0:(n - 1) % len(ds)]) + ((n - 1) // len(ds) * sum(ds)) 
    cnt_same = ds[0:(n - 1) % len(ds)].count(0) + ((n - 1) // len(ds) * ds.count(0))
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_same


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

debug = False

def solve(ds, n, x, m):
    ds = list(ds)
    cnt_zero_in_d = 0
    for i in range(0, len(ds)):
        ds[i] %= m
        if ds[i] == 0:
            cnt_zero_in_d += 1
    a_n = x + sum(ds[0:(n - 1) % len(ds)]) + ((n - 1) // len(ds) * sum(ds)) 
    cnt_same = ds[0:(n - 1) % len(ds)].count(0) + ((n - 1) // len(ds) * cnt_zero_in_d)
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_same


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k,q=map(int,input().split())
D=np.array(list(map(int,input().split())),dtype="i8")

for i in range(q):
    n,x,m=map(int,input().split())
    mD=D%m #元の列のmodを取る
    a=(n-1)//k
    b=(n-1)%k
    ans=0
    cnt=x%m
    for i in range(k):
        if i<b:
            if mD[i]==0: #余り0のとき
                ans+=a+1
            else:
                cnt+=mD[i]*(a+1)
        else:
            if mD[i]==0: #余り0のとき
                ans+=a
            else:
                cnt+=mD[i]*a
    ans+=cnt//m
    print(n-1-ans)

Submission status: Time Limit Exceeded

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

for N,X,M in NXM:
    ds = [d%M for d in D]
    a,b = divmod(N-1,K)
    s = 0
    z = 0
    for i,d in enumerate(ds):
        if i==b:
            sb = s
            zb = z
        if d==0:
            z += 1
        s += d
    x = (X + s*a + sb)//M - X//M
    y = z*a + zb
    print(N-1-x-y)

Submission status: Time Limit Exceeded

Solution code:
k, q= map(int, input().split())
di = list(map(int,input().split()))
Q = [list(map(int,input().split()))for i in range(q)]
le = int(len(di))

for i in range(q):
    n = Q[i][0]
    a0 = Q[i][1]
    m = Q[i][2]

    # dが一周する回数とその端数
    roop = (n-1)//le
    ex = (n-1)%le

     # 余事象を全項数から引く
    an =0
    ans = n - 1   

    # dの和と、０の個数のカウント
    S = 0
    d0 =0
    d = tuple(k%m for k in di)
    for j in range(le):
        k = d[j]
        if k ==0:
            d0 +=1
        else:
            S +=k
        if j < ex:
            an += k
            if k == 0:
                ans -= 1

    an += a0 + S * roop
    ans -= (an//m - a0//m)
    ans -= d0  * roop
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
k, q= map(int, input().split())
di = list(map(int,input().split()))
Q = [list(map(int,input().split()))for i in range(q)]
le = int(len(di))

for i in range(q):
    n = Q[i][0]
    a0 = Q[i][1]
    m = Q[i][2]
    S = 0
    d0 =0
    d = tuple(k%m for k in di)
    for k in d:
        if k ==0:
            d0 +=1
        else:
            S +=k
    
    roop = (n-1)//le
    ex = (n-1)%le
    
    an = a0 + S * roop
    ans = n - 1
    for pp in range(ex):
        an += d[pp]
        if d[pp] == 0:
            ans -= 1
    
    ans -= (an//m - a0//m)
    ans -= d0  * roop
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
k, q= map(int, input().split())
di = list(map(int,input().split()))
Q = [list(map(int,input().split()))for i in range(q)]
le = int(len(di))
for i in range(q):
    n = Q[i][0]
    a0 = Q[i][1]
    m = Q[i][2]
    S = 0
    d0 =0
    d = [k%m for k in di]
    for k in d:
        if k ==0:
            d0 +=1
        else:
            S +=k
    
    roop = (n-1)//le
    ex = (n-1)%le
    
    an = a0 + S * roop
    ans = n - 1
    for pp in range(ex):
        an += d[pp]
        if d[pp] == 0:
            ans -= 1
    
    ans -= (an//m - a0//m)
    ans -= d0  * roop
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
k, q= map(int, input().split())
di = list(map(int,input().split()))
Q = [list(map(int,input().split()))for i in range(q)]
le = int(len(di))
for i in range(q):
    n = Q[i][0]
    a0 = Q[i][1]
    m = Q[i][2]
    
    d0 =0
    d = [k%m for k in di]
    d0 = d.count(0)
    
    roop = (n-1)//le
    ex = (n-1)%le
    
    an = a0 + sum(d) * roop
    ans = n - 1
    for pp in range(ex):
        an += d[pp]
        if d[pp] == 0:
            ans -= 1
    
    ans -= (an//m - a0//m)
    ans -= d0  * roop
    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())
  dm = [a%m for a in d]
  
  zero = (n-1)//len(dm)*dm.count(0) + dm[:(n-1)%len(dm)].count(0)
  
  alast = x + (n-1)//len(dm)*sum(dm) + sum(dm[:(n-1)%len(dm)])
  minus = alast//m - x//m
  
  print(n-1 - zero - minus)

Submission status: Time Limit Exceeded

Solution code:
k, q= map(int, input().split())
di = list(map(int,input().split()))
Q = [list(map(int,input().split()))for i in range(q)]
for i in range(q):
    n = Q[i][0]
    a0 = Q[i][1]
    m = Q[i][2]
    d =[]
    d0 =0
    # d = [k%m for k in di]
    # d0 = d.count(0)
    for qq in range(len(di)):
        d.append(di[qq]%m)
        if d[qq] == 0:
            d0 += 1
    roop = (n-1)//len(d)
    ex = (n-1)%len(d)
    
    an = a0 + sum(d) * roop
    ans = Q[i][0] - 1
    for pp in range(ex):
        an += d[pp]
        if d[pp] == 0:
            ans -= 1
    
    ans -= (an//m - a0//m)
    ans -= d0  * roop
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
k, q= map(int, input().split())
di = list(map(int,input().split()))
Q = [list(map(int,input().split()))for i in range(q)]
for i in range(q):
    n = Q[i][0]
    a0 = Q[i][1]
    m = Q[i][2]
    d = [k%m for k in di]
    d0 = d.count(0)
    roop = (n-1)//len(d)
    ex = (n-1)%len(d)
    
    an = a0 + sum(d) * roop
    ans = Q[i][0] - 1
    for i in range(ex):
        an += d[i]
        if d[i] == 0:
            ans -= 1
    
    ans -= (an//m - a0//m)
    ans -= d0  * roop
    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())
  dm = [a%m for a in d]
  
  zero = (n-1)//len(dm)*sum([a==0 for a in dm]) + sum(a==0 for a in dm[:(n-1)%len(dm)])
  
  alast = x + (n-1)//len(dm)*sum(dm) + sum(dm[:(n-1)%len(dm)])
  minus = alast//m - x//m
  
  print(n-1 - zero - minus)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k,q=map(int,input().split())
D=np.array(list(map(int,input().split())),dtype="i8")

for i in range(q):
    n,x,m=map(int,input().split())
    mD=D%m #元の列のmodを取る
    a=(n-1)//k
    b=(n-1)%k
    ans=0
    ans+=(len(mD)-np.count_nonzero(mD))*a #0の数
    ans+=len(mD[:b])-np.count_nonzero(mD[:b]) #0の数
    cnt=x%m+sum(mD)*a+sum(mD[:b]) #増えた量
    ans+=cnt//m
    print(n-1-ans)

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())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    a=(n-1)//k
    b=(n-1)%k
    ans=0
    ans+=mD.count(0)*a+mD[:b].count(0) #0の数
    cnt=x%m+sum(mD)*a+sum(mD[:b]) #増えた量
    ans+=cnt//m
    print(n-1-ans)

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())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    ans+=mD.count(0)*((n-1)//k)+mD[:((n-1)%k)].count(0) #0の数
    cnt=x%m+sum(mD)*((n-1)//k)+sum(mD[:((n-1)%k)]) #増えた量
    ans+=cnt//m
    print(n-1-ans)

Submission status: Time Limit Exceeded

Solution code:
k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    for d in mD[:((n-1)%k)]: #mod kで余る部分
        if d==0:
            ans+=((n-1)//k)+1
        cnt+=d*(((n-1)//k)+1)
    for d in mD[((n-1)%k):]: #余らない部分
        if d==0:
            ans+=((n-1)//k)
        cnt+=d*((n-1)//k)

    ans+=cnt//m
    A.append(n-1-ans)
for a in A:
    print(a)

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())
  a = [x]
  ans = 0
  for j in range(1, n):
    a.append(a[-1] + d[(j-1)%k])
    if a[-2]%m < a[-1]%m:
      ans+=1
  print(ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    ans+=mD.count(0)*((n-1)//k)+mD[:((n-1)%k)].count(0) #0の数
    cnt=x%m+sum(mD)*((n-1)//k)+sum(mD[:((n-1)%k)]) #増えた量
    ans+=cnt//m
    A.append(n-1-ans)
for a in A:
    print(a)

Submission status: Time Limit Exceeded

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

def solve(n, x, m):
	ds = [x%m for x in D]
	nums = [(n-1)//k + (i < ((n-1)%k)) for i in range(k)]
	zero = sum([num for num, d in zip(nums, ds) if d == 0])
	cum = x%m + sum([num * d for num, d in zip(nums, ds)])
	decr = cum // m
	return n-1 - zero - decr

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

Submission status: Time Limit Exceeded

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

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

    total //= m
    total += s//m * count

    print(n-total-zero_total)


for n, x, m in query:
    answer_query(n-1, x, m)

Submission status: Time Limit Exceeded

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

query = []
for _ in range(q):
    query.append(list(map(int, input().split())))

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

    total //= m
    total += s//m * count

    print(n-total-zero_total)
for n, x, m in query:
    answer_query(n, x, m)

Submission status: Time Limit Exceeded

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

query = []
for _ in range(q):
    query.append(list(map(int, input().split())))

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

    total //= m
    total += s//m * count

    print(n-total-zero_total)
for n, x, m in query:
    answer_query(n, x, m)

Submission status: Time Limit Exceeded

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

query = []
for _ in range(q):
    query.append(list(map(int, input().split())))

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
    rem = n % k
    total = sum(l)%m * count + x%m + sum(l[:rem])
    total //= m
    total += sum(l)//m * count
    zero_total += l[:rem].count(0)

    print(n-total-zero_total)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z1,z2,r,s=0,0,0,0
  for i,d in enumerate(DD):
    s+=d
    if i<v:
      r+=d
      if d==0:
        z1+=1
        z2+=1
    elif d==0:
      z2+=1
  ans-=(z2*u+z1)+(x+s*u+r)//m
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z=DD.count(0)*u
  a_n=x+sum(DD)*u
  for i in range(v):
    a_n+=DD[i]
    if DD[i]==0:
      z+=1
  ans-=z+a_n//m
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  z=DD.count(0)*((n-1)//k)
  a_n=x+sum(DD)*((n-1)//k)
  for i in range((n-1)%k):
    a_n+=DD[i]
    if DD[i]==0:
      z+=1
  ans-=z+a_n//m
  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())
  x %= m
  dmod = [di % m for di in d]
  quot = (n-1) // k
  rest = (n-1) % k
  same = dmod.count(0) * quot + dmod[:rest].count(0)
  a_last = x + sum(dmod) * quot + sum(dmod[:rest])
  beyond = a_last // m
  print(n - 1 - same - beyond)

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())
  dmod = [di % m for di in d]
  same = dmod.count(0) * ((n-1) // k) + dmod[: (n-1) % k].count(0)
  a_last = x + sum(dmod) * ((n-1) // k) + sum(dmod[: (n-1) % k])
  beyond = a_last // m - x // m
  print(n - 1 - same - beyond)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
import sys
input=sys.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())
  dd=[d[i]%m for i in range(k)]
  cnt1=0
  cnt2=0
  for i in range(k):
    if dd[i]==0:
      cnt1+=ceil((n-i-1)/k)
  a=x
  for i in range(k):
    a+=ceil((n-i-1)/k)*dd[i]
  cnt2=a//m-x//m
  print(n-1-cnt1-cnt2)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
k,q=map(int,input().split())
d=list(map(int,input().split()))
for _ in range(q):
  n,x,m=map(int,input().split())
  dd=[d[i]%m for i in range(k)]
  cnt1=0
  cnt2=0
  for i in range(k):
    if dd[i]==0:
      cnt1+=ceil((n-i-1)/k)
  a=x
  for i in range(k):
    a+=ceil((n-i-1)/k)*dd[i]
  cnt2=a//m-x//m
  print(n-1-cnt1-cnt2)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
k,q=map(int,input().split())
d=list(map(int,input().split()))
for _ in range(q):
  n,x,m=map(int,input().split())
  dd=[d[i]%m for i in range(k)]
  cnt1=0
  cnt2=0
  for i in range(k):
    if dd[i]==0:
      cnt1+=ceil((n-i-1)/k)
  a=x
  for i in range(k):
    a+=ceil((n-i-1)/k)*dd[i]
  cnt2=a//m-x//m
  print(n-1-cnt1-cnt2)

Submission status: Time Limit Exceeded

Solution code:
def f_modularness():
    K, Q = [int(i) for i in input().split()]
    D = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    def divceil(a, b):
        return (a + b - 1) // b

    ans = []
    for n, x, m in Queries:
        last, eq = x, 0  # 末項、D_i % m == 0 となる D_i の数
        for i,d in enumerate(D):
            num = divceil(n - 1 - i, K)  # D_i を足すことは何回起きるか？
            last += (d % m) * num
            if d % m == 0:
                eq += num
        ans.append((n - 1) - (last // m - x // m) - eq)
    return '\n'.join(map(str, ans))

print(f_modularness())

Submission status: Time Limit Exceeded

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

K, Q = map(int, input().split())
D = list(map(int, input().split()))
NXM = [list(map(int, input().split())) for _ in range(Q)]

for N, X, M in NXM:
    E = [d % M for d in D]
    cnt, tmp = 0, 0
    for e in E:
        if e > 0:
            cnt += 1
            tmp += e
    cnt *= ((N - 1) // K)
    tmp *= ((N - 1) // K)
    for i in range((N - 1) % K):
        if E[i] > 0:
            cnt += 1
            tmp += E[i]
    tmp += X % M
    print(cnt - tmp // M)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for n, x, m in nxm:
    dd = [e % m for e in d]
    dd = np.array(dd)

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

    print(ans)

Submission status: Time Limit Exceeded

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

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= dd.count(0) * divq
    ans -= dd_r.count(0)

    last = x + sum(dd) * divq + sum(dd_r)
    ans -= last // m - x // m

    print(ans)

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 _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= dd.count(0) * divq
    ans -= dd_r.count(0)

    last = x + sum(dd) * divq + sum(dd_r)
    ans -= last // m - x // m

    print(ans)

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 _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n - 1, k)
    ans -= dd.count(0) * divq
    ans -= dd[:divr].count(0)

    last = x + sum(dd) * divq + sum(dd[:divr])
    ans -= last // m - x // m

    print(ans)

Submission status: Time Limit Exceeded

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

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

Solution code:
# 解説放送

def main():
    from itertools import islice, tee

    k, q = map(int, input().split())
    *d, = map(int, input().split())
    for g in tee(d, q):
        n, x, m = map(int, input().split())
        g = map(lambda x: x % m, g)
        g1, g2, g3 = tee(g, 3)
        rep, rest = divmod(n - 1, k)
        last = x + (sum(g1) * rep) + sum(islice(g2, 0, rest))
        eq = sum(rep + (1 if i < rest else 0) for i, gg in enumerate(g3) if gg == 0)
        ans = (n - 1) - eq - (last // m - x // m)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
K, Q = map(int, input().split())
*D, = map(int, input().split())
for q in range(Q):
    n, x, m = map(int, input().split())
    D1 = [d % m for d in D]
    r = (n - 1) % K
    cnt_0 = D1.count(0) * ((n - 1) // K) + D1[:r].count(0)
    a = x
    # 第n-1項を求める
    b = a + sum(D1) * ((n - 1) // K) + sum(D1[:r])
    # 繰り上がりの回数
    cnt_p = b // m - a // m
    cnt_n = (n - 1) - cnt_0 - cnt_p
    print(cnt_n)

Submission status: Time Limit Exceeded

Solution code:
K, Q = map(int, input().split())
*D, = map(int, input().split())
for q in range(Q):
    n, x, m = map(int, input().split())
    r = (n - 1) % K
    D1r_count0 = 0
    D1_count0 = 0
    D1_sum = 0
    D1r_sum = 0
    for k in range(K):
        if k < r:
            if D[k] % m == 0:
                D1r_count0 += 1
            D1r_sum += D[k] % m
        if D[k] % m == 0:
            D1_count0 += 1
        D1_sum += D[k] % m
    cnt_0 = D1_count0 * ((n - 1) // K) + D1r_count0
    a = x
    # 第n-1項を求める
    b = a + D1_sum * ((n - 1) // K) + D1r_sum
    # 繰り上がりの回数
    cnt_p = b // m - a // m
    cnt_n = (n - 1) - cnt_0 - cnt_p
    print(cnt_n)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

#############
# Main Code #
#############

k,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
  
  return ans
  
    

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

Submission status: Time Limit Exceeded

Solution code:
k,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)