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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
#TLE
k,q=map(int,input().split())
dd=list(map(int,input().split()))
def calc(a,b,m,c,mod):
  #(a,b),(a+m,b+m),(a+2m,b+2m)...(a+cm,b+cm)
  #これらのうち、modをとってa+km<b+kmのもの
  #O(1)またはO(logなにか)
  ans=0
  for i in range(c+1):
    if (a+i*m)%mod<(b+i*m)%mod:ans+=1
  return ans
for _ in range(q):
  n,x,mod=map(int,input().split())
  d=dd.copy()
  v=[x%mod]
  for i in range(k):
    if i!=0:d[i]=(d[i]+d[i-1])%mod
    else:d[0]%=mod
    v.append((v[0]+d[i])%mod)
  if n<=k+1:
    ans=0
    for i in range(1,n):
      if v[i-1]<v[i]:ans+=1
    print(ans)
    break
  ans=0
  if v[0]<v[1]:ans=1
  v=v[1:]
  n-=1
  m=d[-1]
  z=[]
  for i in range(k-1):
    c=n//k-1
    if i+1<n%k:c+=1
    z.append(c)
    ans+=calc(v[i],v[i+1],m,c,mod)
  #print(d)
  #print(v)
  #print(z)
  print(ans)

Submission status: Runtime Error

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

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
    s = min(n, int(math.sqrt(n)*3))
    # s = int(math.sqrt(n))
    comb = [a*i % p for i in range(s)]
    comb.sort()

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

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

    if l < r:
        for i in range(n//s*s, n):
            if l <= a * i % p < r:
                ret += 1
    else:
        for i in range(n // s * s, n):
            if a * i % p < r or l <= a * i % p:
                ret += 1
    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()

    # 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 x == (x+last+1) % m:
        turn += 1
    # 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)