Problem:


Score : 600 points

Problem Statement

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

Process the following q queries in order:

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

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

Constraints

All values in input are integers.

1 \leq k, q \leq 5000

0 \leq d_i \leq 10^9

2 \leq n_i \leq 10^9

0 \leq x_i \leq 10^9

2 \leq m_i \leq 10^9

Input

Input is given from Standard Input in the following format:

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

Output

Print q lines.

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

Sample Input 1

3 1
3 1 4
5 3 2

Sample Output 1

1

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

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

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

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

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

Thus, the response to this query should be 1.

Sample Input 2

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

Sample Output 2

224489796
214285714
559523809



Sample input:
3 1
3 1 4
5 3 2


Sample output:
1

Submission status: Accepted

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

Submission status: Accepted

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

#K,Q = 5,2
#D = np.array([13,13,13,13,13])
#QUERY=[(11,1,2)]

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])
    #print(tD)
    #print(cumsumtD)
    #print(zerocount)
    nloop = (N-1)//K
    rsd = (N-1) - K*nloop
    #print(nloop,rsd)
    temp += nloop * zerocount[-1] + (zerocount[rsd-1] if rsd else 0)
    #print(temp)
    first = X % M
    last = first + sumtD * nloop + (cumsumtD[rsd-1] if rsd else 0)
    #print(sumtD,nloop, cumsumtD,rsd)
    temp += last//M - first//M
    #print(temp)
    ans.append(N-temp-1)
    #print(simple(N,X,M))

for a in ans:
    print(a)

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), dtype=np.int)
for _ in range(q):
  n, x, m = map(int, input().split())
  quot = (n-1) // k
  rest = (n-1) % k
  dmod = d % m
  same = (k - 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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    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): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    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 )
# a = cmb(n,r)

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    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): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    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 )
# a = cmb(n,r)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# MOD = 998244353

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]
    # a[i] < [i + 1] になる数: x → last になるまでに何周するか
    gt = last // m
    # a[i] == a[i + 1] になる数
    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)

Submission status: Accepted

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( ))
    dx = [di%m for di in d]
    ##あまり0をあまりmで処理
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 解説放送

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

Submission status: Accepted

Solution code:
# 解説放送
# tee, isliceをやめた

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

"""
クエリに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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    k,q=MI()
    dd=LI()
    dd=np.array(dd,dtype="i8")
    for _ in range(q):
        n,x,m=MI()
        cc=dd%m
        zall=np.sum(cc==0)
        zlast=np.sum(cc[:(n-1)%k]==0)
        s=np.sum(cc)*((n-1)//k)
        r=np.sum(cc[:(n-1)%k])
        last=x%m+s+r
        no=last//m
        print(n-1-no-zall*((n-1)//k)-zlast)

main()

Submission status: Accepted

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]
    cnt0 = 0
    tmp0 = 0
    for e in E:
        if e > 0:
            cnt0 += 1
            tmp0 += e
    cnt = ((N - 1) // K) * cnt0
    tmp = ((N - 1) // K) * tmp0
    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: Accepted

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

def solve():
    n, x, m = map(int, input().split())
    ans = 0
    rn = (n - 1) % k
    f = x % m
    for i in range(k):
        if d[i] % m == 0:
            continue
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        ans += c
        f += c * (d[i] % m)
    ans -= f // m
    print(ans)

for _ in range(q):
    solve()

Submission status: Accepted

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

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

def sum_count(A):
    S=0
    C=0
    for a in A:
        if a==0:
            C+=1
        else:
            S+=a
    return S,C

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

    D2=[d%m for d in  D]
    S,D0=sum_count(D2)
    R=(n-1)//k
    ANS=R*(k-D0) - (R*S+x%m)//m 
    x2=(x+S*R)%m
    rest=n-R*k-1
    S2,DR0=sum_count(D2[:rest])
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)