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:
import sys
from itertools import accumulate


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


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

Submission status: Time Limit Exceeded

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

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

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

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

    x2=(x+S*R)%m
    rest=n-R*k-1
    S2=sum(D2[:rest])
    DR0=D2[:rest].count(0)
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)

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())
    l = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = x%m
    total += sum(l)*((n-1)//k)
    zero_total = zero*((n-1)//k)

    s = n
    n -= 1
    n -= n//k * k
    t = 0
    for i in range(n):
        t += l[i]

    total += t

    zero_total += l[:n].count(0)
    print(s-1-total//m-zero_total)

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(tuple(map(int, input().split())))

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

    s = n
    n -= 1
    n -= n//k * k
    t = 0
    for i in range(n):
        t += l[i]

    total += t

    zero_total += l[:n].count(0)
    print(s-1-total//m-zero_total)

Submission status: Time Limit Exceeded

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 = sum(d_mod_array)
    mod_total = x % m + d_sum * ((n-1) // k) + sum(d_mod_array[:(n-1)%k])
    reduce_total = mod_total // m

    zero_count = d_mod_array.count(0)
    zero_total = zero_count * ((n-1) // k) + d_mod_array[:(n-1)%k].count(0)
    ans = (n-1) - reduce_total - zero_total
    ans_array.append(str(ans))

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

Submission status: Time Limit Exceeded

Solution code:
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())
        mods=[d%m for d in D]
        S=sum(mods)*((n-1)//k)+x%m
        S+=sum(mods[:(n-1)%k])
        through=S//m
        ans=n-through-1
        ans-=mods.count(0)*((n-1)//k)+mods[:(n-1)%k].count(0)
        print(ans)
main()

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 query in range(q):
    n,x,m=map(int,input().split())

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

    x2=(x+S*R)%m
    rest=n-R*k-1
    S2=sum(D2[:rest])
    DR0=D2[:rest].count(0)
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)

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 = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = x%m
    total += sum(l)*((n-1)//k)
    zero_total = zero*((n-1)//k)

    s = n
    n -= 1
    n -= n//k * k
    t = 0
    for i in range(n):
        t += l[i]
    total += t
    for i in range(n):
        if l[i] == 0:
            zero_total += 1

    print(s-1-total//m-zero_total)

Submission status: Time Limit Exceeded

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]
        roop = (n - 1) // K
        res = n - 1 - (x % m + sum(md) * roop + smda) // m - md.count(0) * roop - mda0
        print(res)


main()

Submission status: Time Limit Exceeded

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

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

for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = sum(d_mod_array)
    mod_total = x % m + d_sum * ((n-1) // k) + sum(d_mod_array[:(n-1)%k])
    reduce_total = mod_total // m

    zero_count = d_mod_array.count(0)
    zero_total = zero_count * ((n-1) // k) + d_mod_array[:(n-1)%k].count(0)
    ans = (n-1) - reduce_total - zero_total
    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()))

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

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

    s = n
    n -= 1
    n -= n//k * k
    for i in range(n):
        total += l[i]

    for i in range(n):
        if l[i] == 0:
            zero_total += 1

    print(s-1-total//m-zero_total)

Submission status: Time Limit Exceeded

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)]
        mda = md[: (n - 1) % K]
        roop = (n - 1) // K
        res = (
            n
            - 1
            - (x % m + sum(md) * roop + sum(mda)) // m
            - md.count(0) * roop
            - mda.count(0)
        )
        print(res)


main()

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 query in range(q):
    n,x,m=map(int,input().split())

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

    x2=(x+S*R)%m

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

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

    print(ANS)

Submission status: Time Limit Exceeded

Solution code:
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())
        mods=[d%m for d in D]

        #Sで総和を作成,何回通過したかを計算
        a=sum(mods)
        S=sum(mods)*((n-1)//k)+x%m
        S+=sum(mods[:(n-1)%k])
        through=S//m

        #カウント回数が答え
        ans=n-through-1
        #カウントしたうち0を省く
        ans-=mods.count(0)*((n-1)//k)+mods[:(n-1)%k].count(0)
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
# スペース区切りの整数入力
k,q = map(int, input().split())

# スペース区切りの整数をリストに入力
d = [int(x) for x in input().split()]

n = []
x = []
m = []

for i in range(q):
    tn,tx,tm = map(int, input().split())
    n.append(tn)
    x.append(tx)
    m.append(tm)

for i in range(q):
    okj = 0
    pa = x[i]
    for j in range(1,n[i]):
        aj = pa + d[(j-1) % k]
        if (pa % m[i]) < (aj % m[i]):
            okj += 1
        pa = aj
    print(okj)

Submission status: Time Limit Exceeded

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

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

for nxm in nxm_array:
    n, x, m = nxm
    d_mod_array = [d % m for d in d_array]
    d_sum = sum(d_mod_array)
    mod_total = x % m + d_sum * ((n-1) // k) + sum(d_mod_array[:(n-1)%k])
    reduce_total = mod_total // m

    zero_count = d_mod_array.count(0)
    zero_total = zero_count * ((n-1) // k) + d_mod_array[:(n-1)%k].count(0)
    ans = (n-1) - reduce_total - zero_total
    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 query in range(q):
    n,x,m=map(int,input().split())

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

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

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

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

    print(ANS)

Submission status: Time Limit Exceeded

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)]
        md0 = md.count(0)
        roop = (n - 1) // K
        amari = (n - 1) % K
        an = x % m + sum(md) * roop + sum(md[:amari])
        minus = an // m
        res = n - 1 - minus - md0 * roop - md[:amari].count(0)
        print(res)


main()

Submission status: Time Limit Exceeded

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)]
        md0 = md.count(0)
        smd = [0]
        for i in range(K):
            smd.append(smd[-1] + md[i])
        roop = (n - 1) // K
        amari = (n - 1) % K
        an = x + smd[-1] * roop + smd[amari]
        minus = an // m - x // m
        res = n - 1 - minus - md0 * roop - md[:amari].count(0)
        print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
K, Q = map(int, input().split())
D = list(map(int, input().split()))
SD = [0]
for i in range(K):
    SD.append(SD[-1] + D[i])

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

Submission status: Time Limit Exceeded

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

K, Q = map(int, readline().split())

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

Ans = [None]*Q
for q in range(Q):
    n, x, mod = map(int, readline().split())
    D2 = [d%mod for d in D]
    res = x + ((n-1)//K)*sum(D2)
    zero = ((n-1)//K)*D2.count(0)
    for i in range((n-1)%K):
        res += D2[i]
        if not D2[i]:
            zero += 1
    minus = res//mod - x//mod
    Ans[q] = n-1 - zero - minus
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    k, q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(q):
        n, x, m = map(int, input().split())
        b = x
        for i in range(k):
            s = (n - 2 - i) // k + 1
            t = D[i] % m
            if t == 0:
                t = m
            b += s * t
        print(n - 1 - (b // m - x // m))
resolve()

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def solve(K, Q, D, NXM):
    Ans = np.empty(Q, dtype=np.int64)
    for q in range(Q):
        n, x, m = NXM[q]
        D_mod = D % m
        cnt_D0 = (D_mod==0).sum()
        sum_D = D_mod.sum()
        t, rem = divmod(n-1, K)
        ans = n-1
        # print(ans)
        ans -= t * cnt_D0
        # print(f"ans={ans},t={t},rem={rem}")

        progress = sum_D * t
        x1 = x%m + progress
        for i in range(rem):
            d = D_mod[i]
            if d == 0:
                ans -= 1
            x1 += d
        # print(f"D={D_mod}")
        # print(f"progress={progress},x1={x1}")

        ans -= x1 // m
        Ans[q] = ans
    return Ans

numba_compile([
    [solve, "i8[:](i8,i8,i8[:],i8[:,:])"]
])

def main():
    K, Q = map(int, input().split())
    D = np.array(input().split(), dtype=np.int64)
    NXM = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(Q, 3)
    Ans = solve(K, Q, D, NXM)
    print("\n".join(map(str, Ans.tolist())))
main()

Submission status: Accepted

Solution code:
def main():
    K, Q = list(map(int, input().split()))
    D = list(map(int, input().split()))
    query_list = [list(map(int, input().split())) for _ in range(Q)]
    ans = [0 for _ in range(Q)]
    for q, query in enumerate(query_list):
        N, X, M = query
        # 増分の数列をmod_dにした数列を考える
        mod_d = [d % M for d in D]
        # a_{j} mod M = a_{j+1} mod M なる j (in {0, ..., N - 2})の個数
        cnt_no_change = 0
        for i, d in enumerate(mod_d):
            # mod_d_{j mod K} = 0 なる j の個数をカウント
            if d != 0:
                continue
            cnt = (N - 2) // K
            if i <= (N - 2) % K:
                cnt += 1
            cnt_no_change += cnt
        # a_{j} mod M > a_{j+1} mod M なるjの個数
        initial_a = X
        final_a = initial_a  # a_{N - 1}
        for i, d in enumerate(mod_d):
            cnt = (N - 2) // K
            if i <= (N - 2) % K:
                cnt += 1
            final_a += cnt * d
        cnt_decrease = final_a // M - initial_a // M
        ans[q] = N - 1 - cnt_no_change - cnt_decrease
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

k, q = map(int, input().split())
_d = list(map(int, input().split()))
for _ in range(q):
    n, x, m = map(int, input().split())
    d = map(lambda xx: xx % m, _d)
    ans = 0
    s = 0
    for i, di in enumerate(d):
        if di == 0:
            ans += math.ceil((n - i - 1) / k)
        else:
            s += di * math.ceil((n - i - 1) / k)
    ans += (s + x) // m - x // m
    print(n - 1 - ans)

Submission status: Accepted

Solution code:
import sys
def LI():
    return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

k,q = LI()
d = LI()

from itertools import accumulate

for _ in range(q):
    n,x,m = LI()
    e = [0] + [d[i] % m for i in range(k)]
    f = list(accumulate(e))
    g = [0] + [d[i] % m == 0 for i in range(k)]
    h = list(accumulate(g))
    p,r = divmod(n - 1,k)
    print(n - 1 - p*h[k] - h[r] - (p*f[k] + f[r] + x % m) // m)

Submission status: Accepted

Solution code:
import sys
def LI():
    return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

k,q = LI()
d = LI()

from itertools import accumulate

for _ in range(q):
    n,x,m = LI()
    e = [0] + [d[i] % m for i in range(k)]
    f = list(accumulate(e))
    g = [0] + [d[i] % m == 0 for i in range(k)]
    h = list(accumulate(g))
    p = (n-1) // k
    r = (n-1) % k
    print(n - 1 - p*h[k] - h[r] - (p*f[k] + f[r] + x % m) // m)

Submission status: Accepted

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

k, q = map(int, input().split())
D = tuple(map(int, input().split()))
for _ in range(q):
  n, x, m = map(int, input().split())
  E = tuple(d%m for d in D)
  temp = n-1
  b = x
  for i, e in enumerate(E, 1):
    c = -(-(n-i)//k)
    if e == 0:
      temp -= c
    b += e*c
  temp -= b//m - x//m
  print(temp)

Submission status: Accepted

Solution code:

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

import numpy as np
def resolve():
    K, Q = map(int, inp().split())
    D = np.array(inp().split(), dtype=np.int64)
    nxm = [list(map(int, inp().split())) for _ in range(Q)]

    for n, x, m in nxm:
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero_acc = np.cumsum(E == 0).astype(np.int64)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    k, q = inp[:2]
    ddd = inp[2:k + 2]
    nnn = inp[k + 2::3]
    xxx = inp[k + 3::3]
    mmm = inp[k + 4::3]
    buf = []
    for n, x, m in zip(nnn, xxx, mmm):
        eee = ddd % m
        acc = np.cumsum(eee)
        zero_acc = np.cumsum(eee == 0)
        loop, rem = divmod(n - 1, k)
        tot = x % m + acc[-1] * loop
        tot_zero = zero_acc[-1] * loop
        if rem > 0:
            tot += acc[rem - 1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        buf.append(n - 1 - dame - tot_zero)
    return buf


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def sub(n,x,m):
    X = 0
    init = x%m
    x%=m
    n -= 1
    if n<=k:
        for i in range(n):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        ans = X
    else:
        for i in range(k):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        diff = (x-init)
        ans = (n//k) * X - (init + (diff*(n//k))) // m
        nn = n-(n//k)*k
        xx = (init + (diff*(n//k))) % m
#         if xx<init:
#             ans -= 1
        for i in range(nn):
            if xx<(xx+d[i])%m:
                ans += 1
            xx = (xx+d[i])%m
    return ans
#         else:
#             ans = (n//k) * X + (init + (diff*(n//k)))
ans = [None]*q
for i in range(q):
    n,x,m = map(int, input().split())
    ans[i] = sub(n,x,m)
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def sub(n,x,m):
    X = 0
    init = x%m
    x%=m
    if n<=k:
        for i in range(n-1):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        ans = X
    else:
        for i in range(k):
            if x<(x+d[i])%m:
                X += 1
            x = (x+d[i])%m
        diff = (x-init)
        ans = ((n-1)//k) * X - (init + (diff*((n-1)//k))) // m
        nn = n-((n-1)//k)*k
        xx = (init + (diff*((n-1)//k))) % m
#         if xx<init:
#             ans -= 1
        for i in range(nn-1):
            if xx<(xx+d[i])%m:
                ans += 1
            xx = (xx+d[i])%m
    return ans
#         else:
#             ans = (n//k) * X + (init + (diff*(n//k)))
ans = [None]*q
for i in range(q):
    n,x,m = map(int, input().split())
    ans[i] = sub(n,x,m)
write("\n".join(map(str, ans)))

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())
    tmp = x
    a = list(map(lambda y: y % m, d))
    c = 0
    s = 0
    c2 = 0
    s2 = 0
    for x in a:
        if x == 0:
            c += 1
        s += x
    for x in a[:(n - 1) % k]:
        if x == 0:
            c2 += 1
        s2 += x
    t = s * ((n - 1) // k) + s2 + tmp % m
    ans = n - 1 - t // m - c * ((n - 1) // k) - c2
    print(ans)

Submission status: Accepted

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


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

for n, x, mod in info:
    d_mod = [d[i] % mod for i in range(k)]
    laps, rem = divmod(n - 1, k)
    start = x % mod
    end = start + sum(d_mod) * laps + sum(d_mod[0:rem])
    ans = n - (end // mod - start // mod + 1)

    # mod_dに0が含まれるときの処理
    is0 = [d_mod[i] == 0 for i in range(k)]
    cnt0 = sum(is0) * laps + sum(is0[0:rem])
    print(ans - cnt0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):

    for i in range(q):
        dmod = [v % m[i] for v in d]
        zero = 0
        c, p = divmod(n[i]-1, k)
        last = x[i]
        # print("dmod", dmod)
        # print("c, p", (c, p))
        for j in range(k):
            if j < p:
                last += (c+1)*dmod[j]
                if dmod[j] == 0:
                    zero += c+1
            else:
                last += c*dmod[j]
                if dmod[j] == 0:
                    zero += c
        print(n[i]-1-(zero + (last//m[i] - x[i]//m[i])))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    k = int(next(tokens))  # type: int
    q = int(next(tokens))  # type: int
    d = [int(next(tokens)) for _ in range(k - 1 - 0 + 1)]  # type: "List[int]"
    n = [int()] * (q)  # type: "List[int]"
    x = [int()] * (q)  # type: "List[int]"
    m = [int()] * (q)  # type: "List[int]"
    for i in range(q):
        n[i] = int(next(tokens))
        x[i] = int(next(tokens))
        m[i] = int(next(tokens))
    solve(k, q, d, n, x, m)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline

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

d = np.array(list(map(int, input().split())), np.int64)

for _ in range(q):
    n, x, m = map(int, input().split())
    tmp = x % m
    d_mod = (d-1) % m + 1 #ex. m = 3 then [0, 1, 2, 3, 4] becomes [3, 1, 2, 3, 1].
    d_cumsummod = np.cumsum(d_mod)
    d_cumsummod = np.concatenate((np.zeros(1, np.int64), d_cumsummod))
    d_q, d_r = divmod(n-1, k)
    tmp += (d_q * d_cumsummod[-1] + d_cumsummod[d_r])
    print((n-1) - tmp // m)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	K, Q = getlist()
	D = getlist()
	for _ in range(Q):
		N, X, M = getlist()
		X %= M
		d = [0] * K
		zeroCount = 0
		for i in range(K):
			var = D[i] % M
			d[i] = var
			if var == 0:
				zeroCount += 1
		Dsum = sum(d)
		p = int((N - 1) // K)
		q = (N - 1) % K
		An = X + Dsum * p
		# print(p, q)
		# print(An)
		# print(d)
		zero = 0
		for i in range(q):
			An += d[i]
			if d[i] == 0:
				zero += 1

		# print(X, An)
		# print(zeroCount * p + zero)
		# print(int(An // M) - int((X + M - 1) // M))
		ans = N - 1 - (zeroCount * p + zero) - (int(An // M) - int(X  // M))
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
import itertools
import collections

input = sys.stdin.readline

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k,q = map(int,input().split())
dbase = list(map(int,input().split()))
for _ in range(q):
  n,x,m = map(int,input().split())
  x %= m
  dls = [d%m for d in dbase]
  q,r = divmod(n-1,k)
  end = x
  minus = 0
  for i in range(k):
    if i < r:
      end += dls[i]*(q+1)
      if dls[i] == 0:
        minus += q+1
    else:
      end += dls[i]*q
      if dls[i] == 0:
        minus += q
  minus += end//m
  print(n-minus-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))#結合
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)

Submission status: Accepted

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    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)//k
            if (n-1) % k >= i+1:
                num += 1  # numはd_iが足される回数
            last += (d[i] % m)*num
            if d[i] % m == 0:
                eq += num

        ans = (n-1)-(last//m-x//m)-eq
        print(ans)


resolve()

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())), dtype=np.int64)
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = np.sum((d[:(n-2) % k+1]-1) % m+1)
        d3 = np.sum((d[(n-2) % k+1:]-1) % m+1)
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()

Submission status: Accepted

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

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

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

        return n-1 - n_same - n_step


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

if __name__ == "__main__":
    run()

Submission status: Accepted

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


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


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


main()