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
k, q = map(int, input().split())
d = np.array(list(map(int, input().split())))
for _ in range(q):
    n, x, m = map(int, input().split())
    dm = d % m
    a = (n - 1) % k
    ans = n - 1
    ans -= np.count_nonzero(dm[:a] == 0) * ((n - 1) // k + 1)
    ans -= np.count_nonzero(dm[a:] == 0) * ((n - 1) // k)
    ans -= (x % m + np.sum(dm[:a]) * ((n - 1) // k + 1) + np.sum(dm[a:]) * ((n - 1) // k)) // m
    print(ans)

Submission status: Accepted

Solution code:
import math


mod=10**9+7

k,q=map(int,raw_input().split())
d=map(int,raw_input().split())
while q:
	q-=1
	n,x,m=map(int,raw_input().split())
	ans=0
	di=(n-1)/k
	cnt=x%m
	left=n-(di*k +1)
	xd=[]
	for i in range(k):
		xd.append(d[i]%m)
	#print xd,ans,left
	for i in range(k):
		lol=0
		if i<left:
			lol=1
		if(xd[i]==0):
			ans+=(lol+di)
		else:
			cnt+=(xd[i]*(lol+di))
	ans+=(cnt/m)
	print n-1-ans

Submission status: Accepted

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

Solution code:
def main():
  import numpy as np
  k, q = map(int, input().split())
  d = np.array(list(map(int, input().split())))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = d % m
    zero_d = k - np.count_nonzero(d_mod)
    d_mod_sum = np.sum(d_mod) + m * zero_d
    rep = (n-1) // k
    rem = (n-1) % k
    zero_rem = len(d_mod[:rem]) - np.count_nonzero(d_mod[:rem])
    rem_sum = np.sum(d_mod[:rem]) + m * zero_rem
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from numpy import int64, count_nonzero

K, Q, *I = map(int, open(0).read().split())
D, NXM = int64(I[:K]), I[K:]

for n, x, m in zip(*[iter(NXM)] * 3):
    q, r = divmod(n - 1, K)
    T = D % m

    a = (K - count_nonzero(T)) * q + r - count_nonzero(T[:r])
    b = (x % m + T.sum() * q + T[:r].sum()) // m

    print(n - 1 - a - b)

Submission status: Accepted

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

for _ in range(q):
    n,x,m = map(int,input().split())
    li = [0]*k
    tmp = 0
    for i in range(k):
        li[i] = d[i]%m
    cnt = x % m
    n -= 1
    for i in range(k):
        cnt += ( n//k + (n%k > i) ) * li[i]
        if li[i] == 0:
            tmp += ( n//k + (n%k > i) )
    print(n-cnt//m - tmp)

Submission status: Accepted

Solution code:
import numpy as np


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

for n, x, m in queries:
    d_mod = d % m
    quotient, rem = divmod(n - 1, k)
    rem_d_mod = d_mod[:rem]
    print(quotient * np.count_nonzero(d_mod) + np.count_nonzero(rem_d_mod)
          - (x % m + quotient * d_mod.sum() + rem_d_mod.sum()) // m)

Submission status: Accepted

Solution code:
import numpy as np


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

for n, x, m in queries:
    d_mod = d % m
    quotient, rem = divmod(n - 1, k)
    rem_d_mod = d_mod[:rem]
    print(quotient * np.count_nonzero(d_mod) + np.count_nonzero(rem_d_mod)
          - (x % m + quotient * np.sum(d_mod) + np.sum(rem_d_mod)) // m)

Submission status: Accepted

Solution code:
import numpy as np


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

for n, x, m in queries:
    d_mod = d % m
    quotient, rem = divmod(n - 1, k)
    rem_d_mod = d_mod[:rem]
    print(n - 1 - (x % m + quotient * np.sum(d_mod) + np.sum(rem_d_mod)) // m
          - quotient * np.count_nonzero(d_mod == 0) - np.count_nonzero(rem_d_mod == 0))

Submission status: Accepted

Solution code:
import numpy as np


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

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

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[k,q]=i2()
d=i2()
for i in range(q):
  [n,x,m]=i2()
  di=[]
  dz=[]
  for i in d:
    di.append(i%m)
    if i%m==0:
       dz.append(1)
    else:
       dz.append(0)
  x=((n-1)//k)*sum(di[:k])+x%m
  if (n-1)%k:
    x+=sum(di[:(n-1)%k])
  ans=n-1-x//m-((n-1)//k)*sum(dz[:k])
  if (n-1)%k:
   ans-=sum(dz[:(n-1)%k])
  print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def solve(k, q, d_list, query_list):

    res = []
    d_arr = np.array(d_list)
    for query in query_list:
        n, x, m = query
        d_arr_mod = (d_arr - 1) % m + 1
        x = x % m
        a_n1 = x + ((n - 1) // k) * d_arr_mod.sum() + d_arr_mod[:((n - 1) % k)].sum()
        res.append(n - 1 - a_n1 // m)

    return res


def main():
    k, q = map(int, input().split())
    d_list = list(map(int, input().split()))
    query_list = [map(int, input().split()) for _ in range(q)]
    res = solve(k, q, d_list, query_list)
    for r in res:
        print(r)


def test():
    assert solve(3, 1, [3, 1, 4], [(5, 3, 2)]) == [1]
    assert solve(7, 3, [27, 18, 28, 18, 28, 46, 1000000000], [
        (1000000000, 1, 7), (1000000000, 2, 10), (1000000000, 3, 12)]) == [224489796, 214285714, 559523809]


if __name__ == "__main__":
    # test()
    main()

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())
    d = [di%m for di in d_]
    ans = n-1
    zero_acc = [0]
    sum_acc = [0]
    
    for di in d:
        zero_acc.append(zero_acc[-1]+(1 if di==0 else 0))
        sum_acc.append(sum_acc[-1]+di)
    
    s, a = divmod(n-1, k)
    ans -= s*zero_acc[-1]+zero_acc[a]
    last = x+s*sum_acc[-1]+sum_acc[a]
    ans -= last//m-x//m
    
    print(ans)

Submission status: Accepted

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

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
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)

Submission status: Accepted

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

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
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    K, q = map(int, input().split())
    D_raw = list(map(int, input().split()))
    for _ in range(q):
        N, x, M = map(int, input().split())

        x %= M
        a = (N-1) % K
        b = (N-1) // K
        D = [0] * K
        zero_num = 0
        zero_num_2 = 0
        for i in range(K):
            d = D_raw[i]%M
            D[i] = d
            if not d:
                zero_num += 1
                if i < a:
                    zero_num_2 += 1
        ans = N - 1 - zero_num * b - zero_num_2 - (sum(D) * b + sum(D[:a]) + x) // M
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
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())
    ans = n - 1
    s = x % m
    dm = [i % m for i in d]
    accum = list(accumulate(dm))
    count = [0] * k
    for i in range(k):
        if dm[i] == 0:
            count[i] += 1
    count = list(accumulate(count))

    s += accum[-1] * ((n-1) // k)
    ans -= count[-1] * ((n-1) // k)
    if (n-1) % k > 0:
        s += accum[(n-1) % k - 1]
        ans -= count[(n-1) % k - 1]
    ans -= s // m
    print(ans)

Submission status: Accepted

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

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

ans_array = []
for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = 0
    d_part = 0
    zero_count = 0
    zero_part = 0
    part = (n-1) % k
    for i,d in enumerate(d_mod_array):
        d_sum += d
        if i < part:
            d_part += d
        if d == 0:
            zero_count += 1
            if i < part:
                zero_part += 1
    mod_total = x % m + d_sum * ((n-1) // k) + d_part
    reduce_total = mod_total // m

    zero_total = zero_count * ((n-1) // k) + zero_part
    ans = (n-1) - reduce_total - zero_total
    ans_array.append(str(ans))

print("\n".join(ans_array))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

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

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

for n, x, m in nxm :
  an = x
  for i in range(k) :
    if d[i] % m != 0 :
      an += ((n - i - 2) // k + 1) * (d[i] % m)
    else :
      an += ((n - i - 2) // k + 1) * m
  print(n - 1 - (an // m - x // m))

Submission status: Accepted

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

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

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

    print(n-total)


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