Problem:


Score : 100 points

Problem Statement

In this problem, you should process T testcases.

For each testcase, you are given four integers N, M, A, B.

Calculate \sum_{i = 0}^{N - 1} floor((A \times i + B) / M).

Constraints

1 \leq T \leq 100,000

1 \leq N, M \leq 10^9

0 \leq A, B < M

Input

Input is given from Standard Input in the following format:

T
N_0 M_0 A_0 B_0
N_1 M_1 A_1 B_1
:
N_{T - 1} M_{T - 1} A_{T - 1} B_{T - 1}

Output

Print the answer for each testcase.

Sample Input 1

5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999

Sample Output 1

3
13
0
314095480
499999999500000000



Sample input:
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999


Sample output:
3
13
0
314095480
499999999500000000

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    ans = 0
    if (a >= m):
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if (b >= m):
        ans += n * (b // m)
        b %= m

    y_max = (a * n + b) // m
    x_max = (y_max * m - b)
    if (y_max == 0):
        return ans
    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans
t=int(input())
for i in range(t):
    n,m,a,b=map(int,input().split())
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0: break
        x_max = b - y_max * m
        res += (n + x_max // a) * y_max
        n, m, a, b = y_max, a, m, x_max % a
    return res

import sys
input = sys.stdin.buffer.readline

T = int(input())
res = [''] * T

for i in range(T):
    n, m, a, b = map(int, input().split())
    res[i] = str(floor_sum(n, m, a, b))

print('\n'.join(res))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0: break
        x_max = b - y_max * m
        res += (n + x_max // a) * y_max
        n, m, a, b = y_max, a, m, x_max % a
    return res

import sys
input = sys.stdin.buffer.readline

T = int(input())
res = [None] * T

for i in range(T):
    n, m, a, b = map(int, input().split())
    res[i] = str(floor_sum(n, m, a, b))

print('\n'.join(res))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        res += (n - 1) * n * (a // m) // 2
        a %= m
        res += n * (b // m)
        b %= m
        y_max = (a * n + b) // m
        if y_max == 0: break
        x_max = y_max * m - b
        res += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    return res

import sys
input = sys.stdin.buffer.readline

T = int(input())
res = [None] * T

for i in range(T):
    n, m, a, b = map(int, input().split())
    res[i] = str(floor_sum(n, m, a, b))

print('\n'.join(res))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0: break
        x_max = y_max * m - b
        res += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    return res

import sys
input = sys.stdin.buffer.readline

T = int(input())
res = [None] * T

for i in range(T):
    n, m, a, b = map(int, input().split())
    res[i] = str(floor_sum(n, m, a, b))

print('\n'.join(res))

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
from cython.parallel cimport prange
from libc.stdio cimport getchar, printf
cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder" nogil:
    cdef long long floor_sum(long long n, long long m, long long a, long long b)
cdef long long cin() nogil:
    cdef long long b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int i, t = cin()
cdef long long n, m, a, b
for i in prange(t, nogil=1):
    n = cin()
    m = cin()
    a = cin()
    b = cin()
    printf('%lld\n', floor_sum(n, m, a, b))
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libc.stdio cimport getchar, printf
cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder":
    cdef long long floor_sum(long long n, long long m, long long a, long long b)
cdef long long cin() nogil:
    cdef long long b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int i, t = cin()
cdef long long n, m, a, b
for i in range(t):
    n = cin()
    m = cin()
    a = cin()
    b = cin()
    printf('%lld\n', floor_sum(n, m, a, b))
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
q = int(input())
for i in range(q):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
import sys
from numba import njit, i8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8, i8), cache=True)
def floor_sum(n, m, a, b):
    ans = 0
    while True:
        if a >= m:
            ans += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            ans += n * (b // m)
            b //= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if not y_max:
            return ans
        ans += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max) % a

T = int(readline())
m = map(int, read().split())
for n, m, a, b in zip(m, m, m, m):
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * (b // m)

    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return ans

    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans

T = int(input())
for t in range(T):
    n, m, a, b = [int(_) for _ in input().split()]
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += a//m * n * (n-1) // 2
            a %= m
        if b >= m:
            res += b//m * n
            b %= m
        Y = (a*n+b) // m
        X = Y*m-b
        if Y == 0:
            return res
        res += (n-(X+a-1)//a) * Y
        n, m, a, b = Y, a, m, -X%a

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += a//m * n * (n-1) // 2
            a %= m
        if b >= m:
            res += b//m * n
            b %= m
        Y = (a*n+b) // m
        X = Y*m-b
        if Y == 0:
            return res
        res += (n+(-X//a)) * Y
        n, m, a, b = Y, a, m, -X%a

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        res += a//m * n * (n-1) // 2
        a %= m
        res += b//m * n
        b %= m
        Y = (a*n+b) // m
        X = Y*m-b
        if Y == 0:
            return res
        res += (n+(-X//a)) * Y
        n, m, a, b = Y, a, m, -X%a

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
t = int(input())

def floor_sum(n,m,a,b):
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2;
        a %= m
    if b >= m:
        ans += n * (b // m)
        b %= m

    y_max = (a * n + b) // m
    x_max = (y_max * m - b)
    if y_max == 0:
        return ans
    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans
for _ in range(t):
    n,m,a,b = map(int,input().split())
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * (b // n)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
      return ans
    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans

t = int(input())
for _ in range(t):
    n, m, a, b = map(int, input().split())
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
def floor_sum(n,m,a,b):
    ans = 0
    if a >= m:
        ans += (n-1)*n*(a//m)//2
        a %= m
    if b >= m:
        ans += n*(b//m)
        b %= m
    y_max = (a*n+b)//m
    x_max = m*y_max-b
    if y_max == 0:
        return ans
    ans += (n-(x_max+a-1)//a)*y_max
    ans += floor_sum(y_max,a,m,(a-x_max%a)%a)    
    return ans

t = int(input())
for i in range(t):
    n,m,a,b = map(int,input().split())
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    out = 0
    while True:
        out += (n - 1) * n * (a // m) // 2 + n * (b // m)
        a %= m
        b %= m
        y_max = (a * n + b) // m
        if y_max == 0:break
        x_max = y_max * m - b
        out += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max % a) % a
    return out

T=int(input())
for i in range(T):
  n,m,a,b=map(int,input().split())
  print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
def Floor_sum(N,M,A,B):
    ANS=0

    if A>=M:
        ANS+=N*(N-1)//2*(A//M)
        A%=M
    if B>=M:
        ANS+=B//M*N
        B%=M

    y_max=(A*N+B)//M
    x_max_divA=y_max*M-B

    if y_max==0:
        return ANS
    else:
        ANS+=Floor_sum(y_max,A,M,A*N-x_max_divA)
        return ANS

T=int(input())
for tests in range(T):
    N,M,A,B=map(int,input().split())
    print(Floor_sum(N,M,A,B))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    def floor_sum(n, m, a, b):
        result = 0
        while True:
            result += (n - 1) * n * (a // m) // 2 + n * (b // m)
            a %= m
            b %= m

            y_max = (a * n + b) // m
            if y_max == 0:
                break

            x_max = y_max * m - b
            result += (n - (x_max + a - 1) // a) * y_max

            n, m, a, b = y_max, a, m, (a - x_max % a) % a
        return result

    t = inp[0]
    ans = np.zeros(t, np.int64)
    for i in range(t):
        n, m, a, b = inp[i * 4 + 1:i * 4 + 5]
        ans[i] = floor_sum(n, m, a, b)
    return ans


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)
    print('compiled', file=sys.stderr)

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

Submission status: Accepted

Solution code:
'''
[AtCoder Library]
sum((a * i + b // m) for i in range(n))
をO(log(n+m+a+b))で計算する。
説明
f(x) = (ax+b)/m とし、 0<y<=f(x) (0<=x<n)の格子点を数える
1.  明らかな整数部を先に計算し a < m, b < m にする
2.  yn = math.floor(f(n))を計算する。これが範囲内でとり得る最大の整数値
3.  f(un) = yn なる実数unを求める。
    下記ソースコードでは xn=a*un として整数xnを扱っている
4.  n - math.ceil(un) が f(i)=yn となる i の個数なので答えにこれを加える。
    下記ソースコードでは math.ceil(un) = math.ceil(xn/a) を (xn + a - 1) // a として計算
5.  軸の入れ替えを行い再帰呼び出しをする。
    傾きを考えると   a←m, m←a
    定義域を考えると n←yn
    y切片を考えると b←a*(math.ceil(un)-un)
    下記ソースコードではa*(math.ceil(un)-un)は(a-xn%a)%aとして計算
'''
def sum_of_floor_of_linear(n, m, a, b):
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * b // m
        b %= m
    yn = (a * n + b) // m
    xn = yn * m - b
    if yn == 0:
        return ans
    ans += (n - (xn + a - 1) // a) * yn
    ans += sum_of_floor_of_linear(yn, a, m, (a - xn % a) % a)
    return ans

t = int(input())
query = []
for _ in range(t):
    query.append(map(int, input().split()))
for n, m, a, b in query:
    print(sum_of_floor_of_linear(n, m, a, b))

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

cdef extern from "/opt/atcoder-stl/atcoder/math.hpp" namespace "atcoder":
    cdef long long floor_sum(long long n, long long m, long long a, long long b)

from libc.stdio cimport scanf, printf
cdef int t, i
cdef long long n, m, a, b
scanf('%d', &t)
for i in range(t):
    scanf('%lld%lld%lld%lld', &n, &m, &a, &b)
    printf('%lld\n', floor_sum(n, m, a, b))
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

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 MI1(): return map(int1, 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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def FloorSum(n, m, a, b):
    ans = 0
    if a >= m:
        ans += (n-1)*n*(a//m)//2
        a %= m
    if b >= m:
        ans += n*(b//m)
        b %= m

    y_max = (a*n+b)//m
    x_max = (y_max*m-b)
    if y_max == 0: return ans
    ans += (n-(x_max+a-1)//a)*y_max
    ans += FloorSum(y_max, a, m, (a-x_max%a)%a)
    return ans

for _ in range(II()):
    n,m,a,b=MI()
    print(FloorSum(n,m,a,b))

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


t = int(input())

def floor_sum(n,m,a,b):
    """sum(((a*i+b)//m) for i in range(n))
    """
    ans = 0
    if a>=m:
        ans += (n-1)*n*(a//m)//2
        a %= m
    if b>=m:
        ans += n*(b//m)
        b %= m
    y_max = (a*n + b) // m
    x_max = y_max*m - b
    if y_max==0:
        return ans
    ans += (n - (x_max+a-1)//a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max%a)%a)
    return ans
for _ in range(t):
    n,m,a,b = list(map(int, input().split()))
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def floor_sum(n,m,a,b):
    res = 0
    while True:
        res += ((n-1)*n*(a//m)>>1) + (b//m)*n
        a %= m
        b %= m
        if a*n+b <= m:
            return res
        Y = (a*n+b)//m
        n,m,a,b = Y,a,m, a*n + b - m*Y

import sys
input = sys.stdin.buffer.readline
T = int(input())
for _ in range(T):
    n,m,a,b = map(int,input().split())
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)


def floor_sum(n, m, a, b):
    ans = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * (b // m)
        b %= m

    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return ans
    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans


T, *queries = map(int, open(0).read().split())
for q in zip(*[iter(queries)] * 4):
    print(floor_sum(*q))

Submission status: Accepted

Solution code:
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        ret += ((n - 1) * n) // 2 * (a // m)
        a %= m
        ret += n * (b // m)
        b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    
    return ret

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

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        if a >= m:
            ret += ((n - 1) * n) // 2 * (a // m)
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n - (x_max + a - 1) // a) * y_max
        n = y_max
        b = -x_max % a
        m, a = a, m

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

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        if a >= m:
            ret += ((n - 1) * n) // 2 * (a // m)
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0:
            return ret
        x_max = y_max * m - b
        ret += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a

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

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        if a >= m:
            ret += ((n - 1) * n) // 2 * (a // m)
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max % a) % a
    
    return ret

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

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        if a >= m:
            ret += ((n - 1) * n) // 2 * (a // m)
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n + (-x_max) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    
    return ret

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

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        if a >= m:
            ret += ((n - 1) * n) // 2 * (a // m)
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, -x_max % a
    
    return ret

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

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def floor_sum(n,m,a,b):  # sum([(a*i+b)//m for i in range(n)])
    res = 0
    res += (a//m)*n*(n-1)//2 + (b//m)*n
    a %= m
    b %= m
    y_max = (a*n+b)//m
    if y_max == 0:
        return res
    x_max = m*y_max-b
    res += (n+(-x_max)//a)*y_max
    res += floor_sum(y_max,a,m,(x_max+a-1)//a*a-x_max)
    return res

import sys
input = sys.stdin.readline
t=int(input())
for i in range(t):
    n,m,a,b=map(int, input().split())
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
from typing import *

# @param b `1 <= b`
# @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
def _inv_gcd(a: int, b: int) -> Tuple[int, int]:
    a %= b
    if a == 0: return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s: int = b; t: int = a
    m0: int = 0; m1: int = 1

    while t:
        u: int = s // t
        s -= t * u
        m0 -= m1 * u # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0: m0 += b // s
    return (s, m0)


def pow_mod(x: int, n: int, m: int) -> int:
    assert 0 <= n and 1 <= m
    if m == 1: return 0
    return pow(x, n, m)


def inv_mod(x: int, m: int) -> int:
    assert 1 <= m
    z = _inv_gcd(x, m)
    assert z[0] == 1
    return z[1]


# (rem, mod)
def crt(r: List[int], m: List[int]) -> Tuple[int, int]:
    assert len(r) == len(m)
    n: int = len(r)
    # Contracts: 0 <= r0 < m0
    r0: int = 0; m0: int = 1
    for i in range(n):
        assert 1 <= m[i]
        r1: int = r[i] % m[i]; m1: int = m[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0, 0)
            continue
        # assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        # (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        # r2 % m0 = r0
        # r2 % m1 = r1
        # -> (r0 + x*m0) % m1 = r1
        # -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        # -> x = (r1 - r0) / g * inv(u0) (mod u1)

        # im = inv(u0) (mod u1) (0 <= im < u1)
        (g, im) = _inv_gcd(m0, m1)

        u1: int = (m1 // g)
        # |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g: return (0, 0)

        # u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        x: int = (r1 - r0) // g % u1 * im % u1

        # |r0| + |m0 * x|
        # < m0 + m0 * (u1 - 1)
        # = m0 + m0 * m1 / g - m0
        # = lcm(m0, m1)
        r0 += x * m0
        m0 *= u1  # -> lcm(m0, m1)
        if r0 < 0: r0 += m0
    
    return (r0, m0)


def floor_sum(n: int, m: int, a: int, b: int) -> int:
    ans: int = 0
    if a >= m:
        ans += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ans += n * (b // m)
        b %= m

    y_max: int = (a * n + b) // m; x_max: int = (y_max * m - b)
    if y_max == 0: return ans
    ans += (n - (x_max + a - 1) // a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ans


# https://atcoder.jp/contests/practice2/tasks/practice2_c
def main() -> None:
    import sys

    t = int(sys.stdin.readline())

    for _ in range(t):
        n, m, a, b = map(int, sys.stdin.readline().split())
        print(floor_sum(n, m, a, b))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    ans = 0
    while 1:
        ans += (n-1)*n//2*(a//m)+n*(b//m)
        a %= m
        b %= m
        y = (a*n+b)//m
        x = b-y*m
        if y == 0:
            return ans
        ans += (x//a+n)*y
        n,m,a,b = y,a,m,x%a
T = int(input())
for i in range(T):
    N,M,A,B = list(map(int,input().split()))
    print(floor_sum(N,M,A,B))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


def floor_sum(n,m,a,b):  # sum((A*i+B)//M for i in range(N))
    res = 0
    if a >= m:
        res += (a//m)*n*(n-1)//2
        a %= m
    if b >= m:
        res += (b//m)*n
        b %= m
    y_max = (a*n+b)//m
    if y_max == 0:
        return res
    x_max = m*y_max-b
    res += (n+(-x_max)//a)*y_max
    res += floor_sum(y_max,a,m,(-x_max) % a)
    return res


T = I()
for i in range(T):
    n,m,a,b = MI()
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


def floor_sum(n,m,a,b):  # sum((A*i+B)//M for i in range(N))
    res = 0
    if a >= m:
        res += (a//m)*n*(n-1)//2
        a %= m
    if b >= m:
        res += (b//m)*n
        b %= m
    y_max = (a*n+b)//m
    if y_max == 0:
        return res
    x_max = m*y_max-b
    res += (n+(-x_max)//a)*y_max
    res += floor_sum(y_max,a,m,(x_max+a-1)//a*a-x_max)
    return res


T = I()
for i in range(T):
    n,m,a,b = MI()
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


def floor_sum(n,m,a,b):  # sum((A*i+B)//M for i in range(N))
    res = 0
    res += (a//m)*n*(n-1)//2 + (b//m)*n
    a %= m
    b %= m
    y_max = (a*n+b)//m
    if y_max == 0:
        return res
    x_max = m*y_max-b
    res += (n+(-x_max)//a)*y_max
    res += floor_sum(y_max,a,m,(x_max+a-1)//a*a-x_max)
    return res


T = I()
for i in range(T):
    n,m,a,b = MI()
    print(floor_sum(n,m,a,b))

Submission status: Accepted

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

def floor_sum(n, m, a, b):
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += (b // m) * n
		b %= m

	y_max = (a * n + b)//m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

for _ in range(int(input())):
	n, m, a, b = map(int, input().split())
	print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
def floor_sum(N, M, A, B):
    ans = 0
    if A >= M:
        ans += (N - 1) * N * (A // M) // 2
        A %= M
    if B >= M:
        ans += N * (B // M)
        B %= M

    y_max = (A * N + B) // M
    if y_max == 0:
        return ans

    x_max = y_max * M - B

    ans += (N + (-x_max // A)) * y_max
    ans += floor_sum(y_max, A, M, (A - x_max % A) % A)

    return ans


T, *NMAB = map(int, open(0).read().split())

for n, m, a, b in zip(*[iter(NMAB)] * 4):
    print(floor_sum(n, m, a, b))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
T = int(input())
NMAB = [tuple(map(int,input().split())) for i in range(T)]

def floor_sum(n,m,a,b):
    ret = 0
    if a >= m:
        ret += (n-1) * n * (a//m) // 2
        a %= m
    if b >= m:
        ret += n * (b//m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0: return ret
    ret += (n - (x_max + a - 1) // a) * y_max
    ret += floor_sum(y_max, a, m, (a - x_max%a)%a)
    return ret

for n,m,a,b in NMAB:
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
def floor_sum(n,m,a,b):
    ans = n*(b//m)
    b %= m
    while True:
        ans += (n-1)*n*(a//m)//2
        a %= m
        if a*n+b < m:
            return ans
        y_max = (a*n + b)//m
        b -= y_max*m #now we have x_max = -(b//a)
        ans += (n + b//a)*y_max
        n = y_max
        b %= a
        m,a = a,m

import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read

T = int(readline())
for _ in range(T):
    n,m,a,b = map(int,readline().split())
    print(floor_sum(n,m,a,b))

Submission status: Accepted

Solution code:
def floor_sum(n,m,a,b):
    ans=0
    if a>=m:
        ans+=(n-1)*n*(a//m)//2
        a%=m
    if b>=m:
        ans+=n*(b//m)
        b%=m
    y_max=(a*n+b)//m
    x_max=(y_max*m-b)
    if y_max==0:
        return ans
    ans+=(n-(x_max+a-1)//a)*y_max
    ans+=floor_sum(y_max,a,m,(a-x_max%a)%a)
    return ans

T=int(input())
for i in range(T):
    N,M,A,B=map(int,input().split())
    print(floor_sum(N,M,A,B))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def floor_sum(n,m,a,b):
    ans = n*(b//m)
    b %= m
    while True:
        ans += (n-1)*n//2*(a//m)
        a %= m
        y_max = (a*n + b)//m
        if y_max == 0:
            return ans
        b -= y_max*m #now we have  x_max = -(b//a)
        ans += (n + b//a)*y_max
        n = y_max
        b %= a
        m,a = a,m

import sys
readline = sys.stdin.readline
read = sys.stdin.read

T = int(readline())
for i in range(T):
    N, M, A, B = map(int, readline().split())
    print(floor_sum(N, M, A, B))