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

Solution (Python):




import math


def pow_mod(x, n, m):
  
  return pow(x, n, m)



def inv_mod(x, m):
  
  return pow(x, m - 2, m)




def crt(r, m):
  n = len(r)
  r0, m0 = 0, 1
  for i in range(n):
    r1 = safe_mod(r[i], m[i])
    m1 = 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
    g, im = inv_gcd(m0, m1)
    u1 = m1 // g
    
    if ((r1 - r0) % g): return (0, 0)
    x = (r1 - r0) // g % u1 * im % u1
    r0 += x * m0
    m0 *= u1
    if r0 < 0: r0 += m0
  return (r0, m0)



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


def safe_mod(x, m):
  x %= m
  if x < 0: x += m
  return x


def inv_gcd(a, b):
  a = safe_mod(a, b)
  if a == 0: return (b, 0)
  s, t = b, a
  m0, m1 = 0, 1
  while t:
    u = s // t
    s -= t * u
    m0 -= m1 * u
    s, t = t, s
    m0, m1 = m1, m0
  if m0 < 0: m0 += b // s
  return (s, m0)



def main():
  T = int(input())
  NMAB = [list(map(int, input().split())) for _ in range(T)]

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

main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools


sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def IF(c, t, f): return t if c else f


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


def main():
    t = I()
    qa = [LI() for _ in range(t)]

    r = []
    for n,m,a,b in qa:
        r.append(floor_sum(n,m,a,b))

    return JA(r, "\n")


print(main())

Solution (Python):
import sys
readline = sys.stdin.readline

def floor_sum_of_linear(N, M, A, B):
    ans = 0
    while True:
        ans += (A//M)*(N-1)*N//2 + (B//M)*N
        A, B = A%M, B%M
        if A*N+B < M:
            return ans
        ymax = (N*A+B)//M
        xmax = -((B-M*ymax)//A)
        ans += (N-xmax)*ymax
        A, B, N, M = M, A*xmax-M*ymax+B, ymax, A 

T = int(readline())
Ans = [None]*T
for qu in range(T):
    Ans[qu] = floor_sum_of_linear(*tuple(map(int, readline().split())))

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

Solution (Python):
def floor_sum(n: int, m: int, a: int, b: int) -> int:
    ans = 0
    while True:
        ans += (n - 1) * n // 2 * (a // m)
        a %= 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 - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (-x_max) % a

import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
    print(floor_sum(*map(int, input().split())))

Solution (Python):
def floor_sum(n: int, m: int, a: int, b: int) -> int:
    ans = 0
    while True:
        ans += (n - 1) * n // 2 * (a // m)
        a %= 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 - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (-x_max) % a

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    print(floor_sum(*map(int, input().split())))

Solution (Python):

import sys


def floor_sum(n, m, a, b):
    ret = 0
    while True:
        if a >= m:
            ret += (a // m) * (n - 1) * n // 2
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        if a * n + b < m:
            return ret
        y_max = (a * n + b) // m
        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


input = sys.stdin.buffer.readline

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

Solution (Python):

import sys

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


input = sys.stdin.buffer.readline

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

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def floor_sum_1(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


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


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


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



T1 = """
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
13
0
314095480
499999999500000000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def floor_sum_1(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


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


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


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



T1 = """
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
13
0
314095480
499999999500000000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def floor_sum_1(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


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


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


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



T1 = """
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
13
0
314095480
499999999500000000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def floor_sum_1(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


def floor_sum(n, m, a, b):
    ret = 0
    while True:
        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
        n = y_max
        m, a, b = a, m, (a - x_max % a) % a


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


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



T1 = """
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
13
0
314095480
499999999500000000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


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


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


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



T1 = """
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
13
0
314095480
499999999500000000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
import sys
input = sys.stdin.readline

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

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

    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numba
from numba import njit, i8
input = sys.stdin.readline

@njit(i8(i8, i8, i8, i8), cache=True)
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 * (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

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

    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

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

    
if __name__ == "__main__":
    main()

Solution (Python):
def FloorSum(n,m,a,b):
    ret = 0
    while True:
        if a>=m:
            ret += (n-1)*n*(a//m)//2
            a%=m

        if b>=m:
            ret += n*(b//m)
            b%=m

        y = (a*n+b)//m
        x = y*m-b

        if y==0:
            return ret

        ret += (n-(x+a-1)//a)*y
        n = y
        b = (a-x%a)%a
        m,a = a,m

T = int(input())

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline


def sum_of_floor(n, m, a, b):
    """sum_{i = 0..n-1} (ai + b) // m を求める。"""
    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 += sum_of_floor(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())

    ans = sum_of_floor(n, m, a, b)
    print(ans)

Solution (Python):
def Floor_Sum(A,B,N,M,K=0):
    """sum_{i=0}^{N-1} floor((A*i+B)/M) を求める.
    """

    if K!=0:
        return Floor_Sum(A,B,N,M)-Floor_Sum(A,B,K-1,M)

    T=0
    P,A=divmod(A,M)
    R,B=divmod(B,M)

    T=P*((N*(N-1))//2)+R*N

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

    if y_max==0:
        return T

    T+=(N-(x_max+A-1)//A)*y_max
    T+=Floor_Sum(M, (A-x_max%A)%A, y_max, A)

    return T

Q=int(input())
X=[0]*Q
for i in range(Q):
    N,M,A,B=map(int,input().split())
    X[i]=Floor_Sum(A,B,N,M)
print("\n".join(map(str,X)))

Solution (Python):
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))

Solution (Python):
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 += n*(b//m)
            b %= m
        if a*n+b < m:
            break
        u = (a*n+b)//m
        v = u*m-b
        res += (n-(v+a-1)//a)*u
        n,m,a,b = u,a,m,(a-v)%a
    return res

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

Solution (Python):


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 _ in range(t):
    n, m, a, b = map(int, input().split())
    ans = floor_sum(n, m, a, b)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
T = int(input())

def FloorSum(n, m, a, b):
  
  res = 0
  if a >= m:
    res += (a // m) * n * (n - 1) // 2
    a %= m
  if b >= m:
    res += n * (b // m)
    b %= m
  if a * n + b < m: return res
  u = (a * n + b) // m
  v = (u * m - b)
  res += (n - (v + a - 1) // a) * u + FloorSum(u, a, m, (a - v) % a)
  return res

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

Solution (Python):




import sys








sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

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)
        bb %= 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

def Main():
    for _ in range(read_int()):
        n, m, a, b = read_ints()
        print(floor_sum(n, m, a, b))

if __name__ == '__main__':
    Main()

Solution (Python):


def sum_of_floor(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 += sum_of_floor(y_max, a, m, (a - x_max % a) % a)
    return ans

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