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:
# -*- coding: utf-8 -*-

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

import math

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

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

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

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

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

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

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

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

def query(n,x,m):
  x %= m
  ans = n-1
  n -= 1
  s1 = 0
  t1 = 0
  for i in range(k):
    s1 += d[i] % m
    if d[i] % m == 0:
      t1 += 1
  s2 = 0
  t2 = 0
  for i in range(n%k):
    s2 += d[i] % m
    if d[i] % m == 0:
      t2 += 1
  x += s1 * (n//k) + s2
  ans -= x//m
  ans -= t1 * (n//k) + t2
  
  print(ans)
  
    

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

Submission status: Time Limit Exceeded

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

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

import math

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

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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 - md.count(0) * roop - mda0
        print(res)


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
k,q=map(int,input().split())
D=list(map(int,input().split()))
for _ in range(q):
    n,x,m=map(int,input().split())
    D_=[d%m for d in D]
    S=sum(D_)
    S_1=S//m
    S_2=S%m
    ans=n-1-S_1*((n-1)//k)-((x%m)+S_2*((n-1)//k)+sum(D_[:(n-1)%k]))//m
    c_0=D_.count(0)*((n-1)//k)+D_[:(n-1)%k].count(0)
    ans-=c_0
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
k,q=map(int,input().split())
D=list(map(int,input().split()))
for _ in range(q):
    n,x,m=map(int,input().split())
    D_=[d%m for d in D]
    S=sum(D_)
    ans=n-1-((x%m)+S*((n-1)//k)+sum(D_[:(n-1)%k]))//m
    c_0=D_.count(0)*((n-1)//k)+D_[:(n-1)%k].count(0)
    ans-=c_0
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i in range(q):
    n, x, m = map(int, input().split())
    lcm = sumd * m // fractions.gcd(sumd, m)
    ans = 0
    a = [x]
    for i in range(n-1):
        j = i%k
        a.append(a[-1] + d[j])
        if (a[-2] % m) < (a[-1] % m):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    t = X%M
    u = 0
    for i in range(K):
        t += ((D[i]-1) % M + 1) * ((N-i-2) // K + 1)
        u += t // M
        t %= M
    print(N - 1 - u)

Submission status: Time Limit Exceeded

Solution code:
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    t = X%M
    for i in range(K):
        t += ((D[i]-1) % M + 1) * ((N-i-2) // K + 1)
    print(N - 1 - t//M)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        count = [0]*k
        D = [0]*k
        c = 0
        for i in range(k):
            D[i] = d[i]%M
            if D[i] == 0:
                c += 1
            count[i] = c
        accum = list(accumulate(D))
        SUMD = accum[-1]
        COUNTD = count[-1]

        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + accum[(N-1)%k-1]
            equal_count = COUNTD*((N-1)//k)+count[(N-1)%k-1]
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        D = [d[i]%M for i in range(k)]
        accum = list(accumulate(D))
        COUNTD = D.count(0)
        SUMD = accum[-1]
        last = 0
        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + accum[(N-1)%k-1]
            equal_count = COUNTD*((N-1)//k)+D[:(N-1)%k].count(0)
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    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: 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) - S//m*R-(S%m*R+x%m)//m 

    x2=(x+S%m*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:
#!/usr/bin/env python3
import sys

def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        D = [d[i]%M for i in range(k)]
        COUNTD = D.count(0)
        SUMD = sum(D)
        last = 0
        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = COUNTD*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + sum(D[:(N-1)%k])
            equal_count = COUNTD*((N-1)//k)+D[:(N-1)%k].count(0)
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    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: Time Limit Exceeded

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

def solve(k: int, q: int, d: "List[int]", n: "List[int]", x: "List[int]", m: "List[int]"):
    for query in range(q):
        N,X,M = n[query],x[query],m[query]
        D = [d[i]%M for i in range(k)]
        SUMD = sum(D)
        last = 0
        if (N-1)%k == 0:
            last = X+((N-1)//k)*SUMD
            equal_count = D.count(0)*((N-1)//k)
        else:
            last = X + SUMD*((N-1)//k) + sum(D[:(N-1)%k])
            equal_count = D.count(0)*((N-1)//k)+D[:(N-1)%k].count(0)
        
        shounari_count = last//M - X//M
        dainari_count = N-shounari_count-equal_count-1
        print(dainari_count)
    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: 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) - S//m*R-(S%m*R+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:
from itertools import accumulate

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

def sof(n, a, b, c):
    if a == 0:
        return (n + 1) * (b // c)
    if a >= c or b >= c:
        return n * (n + 1) // 2 * (a // c) + (n + 1) * (b // c) + sof(n, a % c, b % c, c)
    m = (a * n + b) // c
    return n * m - sof(m - 1, c, c - b - 1, a)

def solve():
    n, x, m = map(int, input().split())
    a = [0] + list(map(lambda i: i % m, accumulate(d)))
    ans = 0
    rn = (n - 1) % k
    for i in range(k):
        u = (x + a[i]) % m
        v = (x + a[i + 1]) % m
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        if u == v:
            continue
        elif u < v:
            ans += c - (sof(c - 1, a[-1], v, m) - sof(c - 1, a[-1], u, m))
        else:
            ans += sof(c - 1, a[-1], u, m) - sof(c - 1, a[-1], v, m)
    print(ans)

for _ in range(q):
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

  print(n - 1 - (s // m) - t)

Submission status: Time Limit Exceeded

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

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

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

    return s-1-total//m-zero_total

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [list(map(int, input().split())) for i in range(q)]
ans = []
for n, x, m in query:
    l = [d[i]%m for i in range(k)]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    total = sum(l)*count + x%m
    rem = n % k
    total += sum(l[:rem])
    zero_total += l[:rem].count(0)
    ans.append(n-total//m-zero_total)
print("\n".join(map(str, 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 = [list(map(int, input().split())) for i in range(q)]

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

    print(n-total//m-zero_total)

Submission status: Time Limit Exceeded

Solution code:
import sys

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()
    for _ in range(q):
        n,x,m=MI()
        sall=spart=0
        zall=zpart=0
        for i,d in enumerate(dd):
            d%=m
            if i<(n-1)%k:
                spart+=d
                if d==0:zpart+=1
            sall+=d
            if d==0:zall+=1
        last=x%m+sall*((n-1)//k)+spart
        no=last//m
        print(n-1-no-zall*((n-1)//k)-zpart)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def search(n, x, m, K, D):
    ini = x % m
    modD = [D[i] % m for i in range(K)]
    roop , rem = (n - 1) // K, (n - 1) % K
    last = ini
    equal = 0
    for i in range(K):
        if i < rem and rem > 0:
            if modD[i] == 0: equal += roop + 1
            else: last += (roop + 1) * modD[i]
        else:
            if modD[i] == 0: equal += roop
            else: last += roop * modD[i]
    up = (last // m) - (ini // m)
    return n - 1 - equal - up

def solve():
    input = sys.stdin.readline
    K, Q = map(int, input().split())
    D = [int(d) for d in input().split()]
    Ans = []
    for _ in range(Q):
        n, x, m = map(int, input().split())
        Ans.append(search(n, x, m, K, D))

    for i, a in enumerate(Ans): print(a)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

K, Q = na()
d = na()

for z in range(Q):
    n, x, m = na()

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1

    lpre = 0
    turn = 0
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        cur = (lpre + v) % m
        if lpre < cur:
            turn += 1
        lpre = cur
    my = turn*m - lpre
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    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=sum(mods)*((n-1)//k)+x%m
        S+=sum(mods[:(n-1)%k])
        through=S//m
        ans=n-through-1
        c = mods[:(n-1)%k].count(0)
        ans-=(c+mods[(n-1)%k:].count(0))*((n-1)//k)+c
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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()
    for _ in range(q):
        n,x,m=MI()
        cc=[d%m for d in dd]
        zall=cc.count(0)
        zlast=cc[:(n-1)%k].count(0)
        s=sum(cc)*((n-1)//k)
        r=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: Time Limit Exceeded

Solution code:
import sys

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()
    for _ in range(q):
        n,x,m=MI()
        cc=[d%m for d in dd]
        zall=cc.count(0)
        zlast=cc[:(n-1)%k].count(0)
        s=sum(cc)*((n-1)//k)
        r=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: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

K, Q = na()
d = na()

# K, Q = 2, 1000
# d = [1, 2]

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]


for z in range(Q):
    n, x, m = na()

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        if l[i] < l[i+1]:
            turn += 1
    my = turn*m - l[-1]
    # print(turn, m, my, n//K, x)
    ans += (my * (n//K) + m-x-1) // m - (m-x-1)//m
    print(ans)

Submission status: Time Limit Exceeded

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

d = input().split()
for i in range(k):
    d[i] = int(d[i])

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

    dd = [0]*k
    DD = [0]*(k+1)
    for i in range(k):
        dd[i] = (d[i]-1)%m + 1
        DD[i+1] = DD[i] + dd[i]
        
    #最後のこう
    
    alast = x + DD[k]*((n-1)//k) + DD[(n-1)%k]
    kuriagari = alast // m - x//m

#    print([x%m, alast, alast%m, n - kuriagari - 1])
    print (n - 1 - kuriagari)

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
    zero_total = zero*((n-1)//k)
    s = n
    n -= 1
    n -= n//k * k
    t = sum(l[:n])
    total += sum(l)*((s-1)//k)
    total += t
    total //= m
    zero_total += l[:n].count(0)
    print(s-1-total-zero_total)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

K, Q = na()
d = na()

# K, Q = 2, 1000
# d = [1, 2]

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]


import math
# count ax < k (mod p), 0 <= x < n
def countle(l, r, a, n, p):
    if l == r:
        return 0
    if n == 0:
        return 0

    a %= p

    # naive = 0
    # ans = 0
    # for i in range(n):
    #     x = a*i%p
    #     if l < r:
    #         if l <= x and x < r:
    #             ans += 1
    #     else:
    #         if x < r or l <= x:
    #             ans += 1

    s = min(n, int(math.sqrt(n)))
    # s = int(math.sqrt(n))
    comb = []
    q = 0
    for i in range(s):
        comb.append(q)
        q += a
        if q >= p:
            q -= p
    comb.sort()
    # print(p, comb)

    ll, rr = l, r
    ret = 0
    b = a * s % p
    for u in range(n//s):
        num = bisect.bisect_left(comb, r) - bisect.bisect_left(comb, l)
        if r < l:
            num += s
        ret += num
        # print(comb, l, r, num)

        l -= b
        r -= b
        if l < 0:
            l += p
        if r < 0:
            r += p

    if ll < rr:
        t = a*(n//s*s) % p
        for i in range(n//s*s, n):
            if ll <= t < rr:
                ret += 1
            t += a
            if t >= p:
                t -= p
    else:
        t = a*(n//s*s) % p
        for i in range(n // s * s, n):
            if t < rr or ll <= t:
                ret += 1
            t += a
            if t >= p:
                t -= p
    # print(ret, ans)
    # assert ret == ans
    return ret

# 2 3 5 7
# 0 2 3 5: 3
# 2 4 5 0: 2
# 4 6 0 2: 2
# 6 1 2 4

# a+k < b+k (mod p)
# a < bなら、k in [-a,p-1-b]
# a > bなら、k in [p-a, p-1-b]
# [-a,-1-b][-b, ...]
# a = bなら無
for z in range(Q):
    n, x, m = na()
    # n, x, m = 10+z, 1+z, 5+z

    # 36, 27, 31

    # 32, 33, 26

    # d0 = x
    # ex = 0
    # for i in range(n-1):
    #     d1 = d0 + d[i%K]
    #     if d0 % m < d1 % m:
    #         ex += 1
    #     d0 = d1

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        # if m-l[i+1] > m-1-l[i]
        if l[i] < l[i+1]:
            turn += 1
    last = m-1-l[-1]
    if 0 == (last+1) % m:
        turn += 1
    # 0 3 6 ... 48 31
    # 0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48
    # % 31 0 <=  <= 2
    # print(ans, turn, last, -x%m, (-x+last+1)%m, l[-1], n//K)
    le = countle(-x%m, (-x+last+1)%m, l[-1], n//K, m)
    # print(le)
    ans += le*turn + (n//K-le)*(turn-1)
    print(ans)
    # assert ans == ex

    # x = turn - (start > last ? 1 : 0)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

K, Q = na()
d = na()

# K, Q = 2, 1000
# d = [1, 2]

u = [0] * (K+1)
for i in range(1, K+1):
    u[i] = u[i - 1] + d[i%K]


import math
# count ax < k (mod p), 0 <= x < n
def countle(l, r, a, n, p):
    if l == r:
        return 0
    if n == 0:
        return 0

    a %= p

    # naive = 0
    # ans = 0
    # for i in range(n):
    #     x = a*i%p
    #     if l < r:
    #         if l <= x and x < r:
    #             ans += 1
    #     else:
    #         if x < r or l <= x:
    #             ans += 1

    s = min(n, int(math.sqrt(n)*4))
    # s = int(math.sqrt(n))
    comb = []
    q = 0
    for i in range(s):
        comb.append(q)
        q += a
        if q >= p:
            q -= p
    comb.sort()
    # print(p, comb)

    ll, rr = l, r
    ret = 0
    b = a * s % p
    for u in range(n//s):
        num = bisect.bisect_left(comb, r) - bisect.bisect_left(comb, l)
        if r < l:
            num += s
        ret += num
        # print(comb, l, r, num)

        l -= b
        r -= b
        if l < 0:
            l += p
        if r < 0:
            r += p

    if ll < rr:
        t = a*(n//s*s) % p
        for i in range(n//s*s, n):
            if ll <= t < rr:
                ret += 1
            t += a
            if t >= p:
                t -= p
    else:
        t = a*(n//s*s) % p
        for i in range(n // s * s, n):
            if t < rr or ll <= t:
                ret += 1
            t += a
            if t >= p:
                t -= p
    # print(ret, ans)
    # assert ret == ans
    return ret

# 2 3 5 7
# 0 2 3 5: 3
# 2 4 5 0: 2
# 4 6 0 2: 2
# 6 1 2 4

# a+k < b+k (mod p)
# a < bなら、k in [-a,p-1-b]
# a > bなら、k in [p-a, p-1-b]
# [-a,-1-b][-b, ...]
# a = bなら無
for z in range(Q):
    n, x, m = na()
    # n, x, m = 10+z, 1+z, 5+z

    # 36, 27, 31

    # 32, 33, 26

    # d0 = x
    # ex = 0
    # for i in range(n-1):
    #     d1 = d0 + d[i%K]
    #     if d0 % m < d1 % m:
    #         ex += 1
    #     d0 = d1

    n -= 1

    rem = n%K
    pre = m-1
    x %= m
    ans = 0
    for i in range(rem):
        pre = x
        x = (x + d[i]) % m
        if pre < x:
            ans += 1
    # print(x, n, K, rem, ans)

    l = [0]
    # print(d[rem:] +  d[:rem])
    for v in d[rem:] + d[:rem]:
        l.append((l[-1] + v) % m)
    # print(l)
    turn = 0
    for i in range(len(l)-1):
        # if m-l[i+1] > m-1-l[i]
        if l[i] < l[i+1]:
            turn += 1
    last = m-1-l[-1]
    if 0 == (last+1) % m:
        turn += 1
    # 0 3 6 ... 48 31
    # 0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48
    # % 31 0 <=  <= 2
    # print(ans, turn, last, -x%m, (-x+last+1)%m, l[-1], n//K)
    le = countle(-x%m, (-x+last+1)%m, l[-1], n//K, m)
    # print(le)
    ans += le*turn + (n//K-le)*(turn-1)
    print(ans)
    # assert ans == ex

    # x = turn - (start > last ? 1 : 0)