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

Solution (Python):
import numpy as np

def main():
    k, q = [int(x) for x in input().split()]
    d = np.fromstring(input(), np.int64, sep=' ')

    def solve1(d, n):
        
        zero = np.where(d == 0)[0]
        n_zero = zero.shape[0] * ((n - 1) // k)
        n_zero += np.count_nonzero(zero < (n - 1) % k)
        return n_zero

    def solve2(d, n, x, m):
        
        a_max = np.sum(d) * ((n - 1) // k) + np.sum(d[:(n - 1) % k])
        return (a_max + x) // m - x // m

    for _ in range(q):
        n, x, m = [int(x) for x in input().split()]
        dm = d % m
        n_zero = solve1(dm, n)
        n_dec = solve2(dm, n, x, m)
        print(n - 1 - n_zero - n_dec)

if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
import sys
import numpy as np
input = sys.stdin.buffer.readline
K, Q= map(int,input().split())
D = np.array(list(map(int,input().split()))).astype(np.int64)
QUERY = [list(map(int,input().split())) for i in range(Q)]





def simple(N,X,M):
    S = [X]
    for i in range(N-1):
        S.append((S[-1] + D[i % K]))
    temp = 0
    modS = [s % M for s in S]
    for a,b in zip(modS,modS[1:]):
        if a < b:
            temp += 1
    return temp

ans = []
for query in QUERY: 
    N,X,M = query
    temp = 0
    tD = D % M
    sumtD = np.sum(tD)
    cumsumtD = np.cumsum(tD)
    zerocount = np.cumsum([tD == 0])
    
    
    
    nloop = (N-1)//K
    rsd = (N-1) - K*nloop
    
    temp += nloop * zerocount[-1] + (zerocount[rsd-1] if rsd else 0)
    
    first = X % M
    last = first + sumtD * nloop + (cumsumtD[rsd-1] if rsd else 0)
    
    temp += last//M - first//M
    
    ans.append(N-temp-1)
    

for a in ans:
    print(a)

Solution (Python):

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,n,k):
            if(n<k):
                return 0
            if(n<0 or k<0 ):
                return 0
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod
    return CONV()


def main():
    k,q = isRaw()
    ds_orig =isRaw()
    for qidx in range(q):
        n,x,m = isRaw()
        ds = [d%m for d in ds_orig]
        numPluses = [((n-1)//k)+(0 if idx >= (n-1)%k else 1) for idx in range(k)]
        totals = x%m
        numGe =0
        for idx,d in enumerate(ds):
            totals += d*numPluses[idx]
            if totals >= m:
                numGe += totals//m
                totals = totals%m
            if d==0:
                numGe += numPluses[idx]
        print(n-1-numGe)
    return n-1-numGe



if __name__ == "__main__":
    main()

Solution (Python):
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 - np.count_nonzero(dmod)) * quot + rest - np.count_nonzero(dmod[:rest])
  a_last = x % m + dmod.sum() * quot + dmod[:rest].sum()
  beyond = a_last // m
  print(n - 1 - same - beyond)

Solution (Python):
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())
  x %= m
  dq = [y % m for y in d]
  
  for i in range(K): dq[i] += (dq[i] == 0) * m
  res = (sum(dq) * ((n - 1) // K) + sum(dq[: (n - 1) % K]) + x) // m
  print(n - 1 - res)

Solution (Python):
"""
F
"""
K,Q=map(int,input().split())

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

que=[list(map(int,input().split())) for i in range(Q)]

for n,x,mod in que:
    
    x%=mod
    d=[]
    if D[0]%mod==0:
        d.append(mod)
    else:
        d.append(D[0]%mod)
        
    for i in range(1,K):
        if D[i]%mod==0:
            d.append(d[-1]+mod)
        else:
            d.append(d[-1]+D[i]%mod)

    s=d[-1]
    num=x+s*((n-2)//K)+d[(n-2)%K]
    print(n-1-num//mod)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = []
    for j in range(k):
        
        po.append(d[j] % mm)

    for j in range(k):
        if po[j] == 0:
            ccc = ((n-1)//k)
            if (n-1)%k >= j+1:
                ccc += 1
            co += ccc

    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += (pp//mm) - (x//mm)
    
    print((n-co-1))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = []
    for j in range(k):
        po.append(d[j] % mm if d[j] % mm > 0 else mm)

    """
    for j in range(k):
        if po[j] == 0:
            ccc = ((n-1)//k)
            if (n-1)%k >= j:
                ccc += 1
            co += ccc
    """
    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += (pp//mm) - (x//mm)
    
    print((n-co-1))

Solution (Python):
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())
    dm=[di%m if di%m>0 else m for di in d]
    oa=on=0
    for i,a in enumerate(dm):
        oa+=a
        if i+1==(n-1)%k: on=oa
    first = x
    last = x + (oa * ((n-1)//k)) + on
    print(n-1 - (last//m - first//m))

Solution (Python):
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)]
  for i in range(k):
    if dd[i]==0:
      dd[i]=m
  s=x%m+sum(dd)*((n-1)//k)+sum(dd[:(n-1)%k])
  print(n-1-s//m)

Solution (Python):
import numpy as np

k,q = map(int,input().split())
d = np.array(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):
    d_ = d%m[i]
    j = np.sum(d_ * ((n[i]-1)//k)) + np.sum(d_[:(n[i]-1)%k])
    s = np.sum(np.sum(d_==0) * ((n[i]-1)//k)) + np.sum(d_[:(n[i]-1)%k]==0)
    count = n[i] - 1 - (j+x[i]%m[i])//m[i] - s
    print(count)

Solution (Python):
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  
        for i,d in enumerate(D):
            num = divceil(n - 1 - i, K)  
            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())

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



k, q = LI()
D = LI()
for _ in range(q):
    n, x, m = LI()
    ret = x
    D_m = [d % m for d in D]
    zero_or_one = [0] + list(accumulate([1 if d == 0 else 0 for d in D_m]))
    Dm_acc = [0] + list(accumulate(D_m))
    ret = x + (n - 1) // k * Dm_acc[-1] + Dm_acc[(n - 1) % k]
    zero_ret = (n - 1) // k * zero_or_one[-1] + zero_or_one[(n - 1) % k]
    print(n - 1 - (ret // m - x // m) - zero_ret)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



k, q = LI()
D = LI()
for _ in range(q):
    n, x, m = LI()
    ret = x
    D_m = [d % m for d in D]
    zero_or_one = list(accumulate([1 if d == 0 else 0 for d in D_m]))
    Dm_acc = list(accumulate(D_m))
    ret = x + (n - 1) // k * Dm_acc[-1]
    zero_ret = (n - 1) // k * zero_or_one[-1]
    if (n - 1) % k:
        ret += Dm_acc[(n - 1) % k - 1]
        zero_ret += zero_or_one[(n - 1) % k - 1]
    print(n - 1 - (ret // m - x // m) - zero_ret)

Solution (Python):
import os
import sys

import numpy as np

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

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


K, Q = list(map(int, sys.stdin.buffer.readline().split()))
D = list(map(int, sys.stdin.buffer.readline().split()))
NXM = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

D = np.array(D, dtype=int)


def solve(n, x, m):
    cum = (D % m).cumsum()
    zerocum = (D % m == 0).cumsum()
    last = x % m + cum[-1] * ((n - 2) // K) + cum[(n - 2) % K]
    
    gt = last // m
    
    eq = zerocum[-1] * ((n - 2) // K) + zerocum[(n - 2) % K]
    return n - 1 - gt - eq


for n, x, m in NXM:
    ans = solve(n, x, m)
    print(ans)

Solution (Python):
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)

Solution (Python):

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( ))
    dx = [di%m for di in d]
    
    for i in range(k):
        if dx[i]==0:
            dx[i]=m
    sm = x%m+sum(dx)*((n-1)//k)+sum(dx[:(n-1)%k])
    print(n-1 -sm//m)

Solution (Python):
import numpy as np

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

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

    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)

Solution (Python):

k,q = map(int,input().split())
d = list(map(int,input().split()))
for _ in range(q):
    n,x,m = map(int,input().split())
    e = list(map(lambda x:(x-1)%m+1,d))
    s = sum(e)*((n-1)//k) + sum(e[:(n-1)%k])
    tmp = (s+x)//m - x//m
    print(n-1-tmp)

Solution (Python):


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-1)%m+1,d))
    s = sum(e)*((n-1)//k) + sum(e[:(n-1)%k])
    tmp = (s+x)//m - x//m
    print(n-1-tmp)

Solution (Python):
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 _ in range(Q)]

for n, x, mod in Query:
    Td = []
    for d in D:
        Td.append(d%mod)
    Init = [0]
    zero_count = 0
    zero_tmp = 0
    for i, d in enumerate(Td):
        Init.append(Init[-1]+d)
        if d == 0:
            zero_count += 1
            if i < (n-1)%K:
                zero_tmp += 1
    c = Init.pop()
    last = x + c*((n-1)//K) + Init[(n-1)%K]
    over_count = last//mod - x//mod
    print((n-1)-over_count-zero_count*((n-1)//K)-zero_tmp)

Solution (Python):


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-1)%m+1,d))
    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-tmp)

Solution (Python):


def solve():
    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)
        yield ans


def main():
    print(*solve(), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    k, q = map(int, input().split())
    *d, = map(int, input().split())
    for _ in range(q):
        n, x, m = map(int, input().split())
        *g, = map(lambda x: x % m, d)
        rep, rest = divmod(n - 1, k)
        last = x + (sum(g) * rep) + sum(g[:rest])
        eq = sum(rep + (1 if i < rest else 0) for i, gg in enumerate(g) if gg == 0)
        ans = (n - 1) - eq - (last // m - x // m)
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    k,q = LI()
    d = LI()
    for _ in range(q):
        n,x,m = LI()
        a = [((i-1)%m)+1 for i in d]
        S = sum(a)
        r = (n-1)//k
        s = S*r+(x%m)
        for i in range((n-1)%k):
            s += a[i]
        print(n-1-(s//m))
    return


if __name__ == "__main__":
    solve()

Solution (Python):
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
    
    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)

Solution (Python):

"""
クエリにO(k)で答えたい
あらかじめdをmでmodしておく

aj >= aj+1 (すなわち、jが条件を満たさない)となるのは、
dが0の時と、aj+d > m の時である。

よって、0が出る回数 & mの倍数をいくつ超えるかを計算すればよい
それをnから引く
"""

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

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

for loop in range(q):

    n,x,m = map(int,input().split())
    x %= m

    nd = []
    for i in d:
        nd.append(i % m)

    znum = [0]
    lsum = [0]

    for i in nd:
        if i == 0:
            znum.append(znum[-1] + 1)
        else:
            znum.append(znum[-1])

        lsum.append(lsum[-1] + i)


    zpick = ((n-1) // k) * znum[-1] + znum[(n-1) % k]
    lpick = (x + ((n-1) // k) * lsum[-1] + lsum[(n-1) % k]) // m

    print (n-1 - zpick - lpick)

Solution (Python):






import math





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





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





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)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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-1)%m+1 for d in D]
  tmp = x; s = (n-1) // k
  for i, di in enumerate(DD):
    tmp += di*(s + int((n-1)%k > i))
  print(n-1-(tmp//m-x//m))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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-1+m)%m+1 for d in D]
  tmp = x; s = (n-1) // k
  for i, di in enumerate(DD):
    tmp += di*(s + int((n-1)%k > i))
  print(n-1-(tmp//m-x//m))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

for qi in range(q):
    n, x, m = map(int, input().split())
    last = x
    eq = 0
    for i in range(k):
        num = ((n-1-i)+(k-1))//k
        last += (d[i]%m) * num
        if d[i]%m == 0: eq += num
    ans = (n-1) - (last//m - x//m) - eq
    print(ans)

Solution (Python):
import sys
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-1)//k)*np.sum(d_modm==0) + np.sum((d_modm==0)[:(n-1)%k])
		last = x + ((n-1)//k)*np.sum(d_modm) + np.sum((d_modm)[:(n-1)%k])
		ans[i]=(n-1)-zero-(last//m-x//m)
	printV(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys


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)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()

Solution (Python):
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)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md.count(0) * roop - mda0
        print(res)


main()

Solution (Python):
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)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + sum(md) * roop + smda) // m - md0 * roop - mda0
        print(res)


main()

Solution (Python):
k, q = map(int, input().split())
d = list(map(int, input().split()))
for i in range(q):
    n, x, m = map(int, input().split())
    d2 = [d[i] % m for i in range(k)]
    sum_d = [0] * (k + 1)
    count_d = [0] * (k + 1)
    for i in range(k):
        sum_d[i + 1] = sum_d[i] + d2[i]
        if d2[i] == 0:
            count_d[i + 1] = count_d[i] + 1
        else:
            count_d[i + 1] = count_d[i]
    a = (n - 1) // k
    b = (n - 1) % k
    c = (x + sum_d[k] * a + sum_d[b]) // m - (x // m)
    print(n - 1 - c - count_d[k] * a - count_d[b])

Solution (Python):
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)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()