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):
def floor_linear_sum(n,m,a,b):
    """
    returns sum((a*i+b)//m for i in range(n))
    """
    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:
            return res
        nx_max = b - y_max*m
        res += (n + nx_max//a)*y_max
        n,m,a,b = y_max, a, m, nx_max%a

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

T = int(readline())
m = map(int,read().split())
for t in zip(m,m,m,m):
    print(floor_linear_sum(*t))

Solution (Python):
def floor_linear_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:
            return res
        x_max = y_max*m-b
        res += (n - (x_max + a - 1)//a)*y_max
        n,m,a,b = y_max, a, m, (a-x_max)%a

T = int(input())
for _ in range(T):
    print(floor_linear_sum(*map(int,input().split())))

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

    while y_max:
        x_max = y_max*m-b
        res += (n - (x_max + a - 1)//a)*y_max
        n,m,a,b = y_max, a, m, (a-x_max)%a
        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
    return res

T = int(input())
for _ in range(T):
    print(floor_linear_sum(*map(int,input().split())))

Solution (Python):
def floor_linear_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:
            return res
        x_max = y_max*m-b
        res += (n - (x_max + a - 1)//a)*y_max
        n,m,a,b = y_max, a, m, (a-x_max)%a

T = int(input())
for _ in range(T):
    print(floor_linear_sum(*map(int,input().split())))

Solution (Python):
T = int(input())

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

    yMax = (a * n + b) // m
    xMax = yMax * m - b
    if yMax == 0:
        return result
    result += (n - (xMax + a - 1) // a) * yMax
    result += floor_sum(yMax, a, m, (a - xMax % a) % a)
    return result
  
  
for _ in range(T):
  n, m, a, b = map(int,input().split())
  print(floor_sum(n, m, a, b))

Solution (Python):
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


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


def main():
    t = int(read())
    for _ in range(t):
        print(floor_sum(*map(int, read().split())))


if __name__ == '__main__':
    main()

Solution (Python):
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
n=int(input())
ans=[]
for _ in range(n):
  n,m,a,b=map(int,input().split())
  ans+=[floorsum(n,m,a,b)]
print(*ans,sep='\n')

Solution (Python):

def floor_sum(n, m, a, b):
    res = 0
    while True:
        res += (n * (b // m)) + (a // m) * (n * (n - 1) // 2)
        a %= m
        new_n = (a * n + b) // m
        new_m = a
        new_a = m
        if not new_n:
            return res
        b -= new_n * m
        res += (b // a + n) * new_n
        new_b = b % a
        n, m, a, b = new_n, new_m, new_a, new_b


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

Solution (Python):
mod = 1000000007
eps = 10**-9


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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def floor_sum(n, m, a, b):
    ans = 0
    while True:
        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

import sys
input = sys.stdin.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):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__math_code = """
import typing


class Barrett:
    '''
    Fast moduler by barrett reduction
    Reference: https://en.wikipedia.org/wiki/Barrett_reduction
    NOTE: reconsider after Ice Lake
    '''

    def __init__(self, m: int) -> None:
        self._m = m
        self._im = ((1 << 64) - 1) / m + 1

    def umod(self) -> int:
        return self._m

    def mul(self, a: int, b: int) -> int:
        '''
        [1] m = 1
        a = b = im = 0, so okay

        [2] m >= 2
        im = ceil(2^64 / m)
        -> im * m = 2^64 + r (0 <= r < m)
        let z = a*b = c*m + d (0 <= c, d < m)
        a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        c*r + d*im < m*m + m*im < m*m + 2^64 + m <= 2^64 + m*(m+1) < 2^64 * 2
        ((ab * im) >> 64) == c or c + 1
        '''

        z = a * b
        x = (z * self._im) >> 64
        v = z - x * self._m
        if self._m <= v:
            v += self._m
        return v


def _is_prime(n: int) -> bool:
    '''
    Reference:
    M. Forisek and J. Jancina,
    Fast Primality Testing for Integers That Fit into a Machine Word
    '''

    if n <= 1:
        return False
    if n == 2 or n == 7 or n == 61:
        return True
    if n % 2 == 0:
        return False

    d = n - 1
    while d % 2 == 0:
        d /= 2

    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = y * y % n
            t <<= 1
        if y != n - 1 and t % 2 == 0:
            return False
    return True


def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    
    
    
    
    s = b
    t = a
    m0 = 0
    m1 = 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 _primitive_root(m: int) -> int:
    if m == 2:
        return 1
    if m == 167772161:
        return 3
    if m == 469762049:
        return 3
    if m == 754974721:
        return 11
    if m == 998244353:
        return 3

    divs = [2] + [0] * 19
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2

    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2

    if x > 1:
        divs[cnt] = x
        cnt += 1

    g = 2
    while True:
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                break
        else:
            return g
        g += 1
"""

atcoder._math = types.ModuleType('atcoder._math')
exec(_atcoder__math_code, atcoder._math.__dict__)


_atcoder_math_code = """
import typing




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

    return pow(x, n, m)


def inv_mod(x: int, m: int) -> int:
    assert 1 <= m

    z = atcoder._math._inv_gcd(x, m)

    assert z[0] == 1

    return z[1]


def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    n = len(r)

    
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1 <= m[i]
        r1 = 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

        

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

        
        g, im = atcoder._math._inv_gcd(m0, m1)

        u1 = m1 // g
        
        if (r1 - r0) % g:
            return (0, 0)

        
        x = (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  
        if r0 < 0:
            r0 += m0

    return (r0, m0)


def floor_sum(n: int, m: int, a: int, b: int) -> int:
    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
"""

atcoder.math = types.ModuleType('atcoder.math')
exec(_atcoder_math_code, atcoder.math.__dict__)
floor_sum = atcoder.math.floor_sum






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

Solution (Python):
import sys
from numba import njit, i8


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


def main():
    t = int(sys.stdin.buffer.readline())
    ans = [0]*t
    for i, x in enumerate(sys.stdin.buffer.readlines()):
        n, m, a, b = map(int, x.split())
        ans[i] = floor_sum(n, m, a, b)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from numba import njit, i8


@njit((i8, i8, i8, i8), cache=True)
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  
        ans += (n + b//a)*y_max
        b %= a
        m, a, n = a, m, y_max


def main():
    t = int(sys.stdin.buffer.readline())
    ans = [0]*t
    for i, x in enumerate(sys.stdin.buffer.readlines()):
        n, m, a, b = map(int, x.split())
        ans[i] = floor_sum(n, m, a, b)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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  
        ans += (n + b//a)*y_max
        b %= a
        m, a, n = a, m, y_max


def main():
    t = int(sys.stdin.buffer.readline())
    ans = [0]*t
    for i, x in enumerate(sys.stdin.buffer.readlines()):
        n, m, a, b = map(int, x.split())
        ans[i] = floor_sum(n, m, a, b)
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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  
        ans += (n + b//a)*y_max
        b %= a
        m, a, n = a, m, y_max


def main():
    t = int(sys.stdin.buffer.readline())
    for x in sys.stdin.buffer.readlines():
        n, m, a, b = map(int, x.split())
        res = floor_sum(n, m, a, b)
        print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from numba import njit, i8


@njit((i8, i8, i8, i8), cache=True)
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  
        ans += (n + b//a)*y_max
        b %= a
        m, a, n = a, m, y_max


def main():
    t = int(sys.stdin.buffer.readline())
    for x in sys.stdin.buffer.readlines():
        n, m, a, b = map(int, x.split())
        res = floor_sum(n, m, a, b)
        print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from numba import njit, i8


@njit((i8, i8, i8, i8), cache=True)
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  
        ans += (n + b//a)*y_max
        b %= a
        m, a, n = a, m, y_max


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):
import sys


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  
        ans += (n + b//a)*y_max
        n = y_max
        b %= a
        m, a = a, m


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 solve(n, m, a, b):
    if n == 0:
        return 0
    res = 0
    if a >= m:
        res += (n-1) * n // 2 * (a // m)
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    p = (a*n + b) // m
    q = p*m - b
    return res + solve(p, a, m, a*n-q)

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

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 += 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):
header_code = """








namespace aclython {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = atcoder::internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l, S b) {
        return max_right(l, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int max_right(int l, S b, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]), b)) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]), b)) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r, S b) {
        return min_left(r, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int min_left(int r, S b, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm), b)) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm), b)) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};



int min_op(int n, int m){
    return std::min(n, m);
}

int min_e(){
    return (int)1e9;
}

struct segtree_min {
    public:
        segtree_min() : segtree_min(0) {}
        segtree_min(int n) : segtree_min(std::vector<int>(n, min_e())) {}
        segtree_min(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, min_op, min_e> seg;
};

int max_op(int n, int m){
    return std::max(n, m);
}

int max_e(){
    return 0;
}

struct segtree_max {
    public:
        segtree_max() : segtree_max(0) {}
        segtree_max(int n) : segtree_max(std::vector<int>(n, max_e())) {}
        segtree_max(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, max_op, max_e> seg;
};

using mint = atcoder::modint998244353;

struct S {
    mint a;
    int size;
    S(mint _a, int _size) : a(_a) ,size(_size) {}
    S(int _a, int _size) : a(_a) ,size(_size) {}
    S(const S &s) : a(s.a), size(s.size) {}
    int get_a() { return (int)a.val(); }
};

struct F {
    mint a, b;
    F(mint _a, mint _b) : a(_a), b(_b) {}
    F(int _a, int _b) : a(_a), b(_b) {}
    F(const F &f) : a(f.a), b(f.b) {}
    int get_a() { return (int)a.val(); }
    int get_b() { return (int)b.val(); }
};

S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }

S e() { return S{0, 0}; }

S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }

F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }

F id() { return F{1, 0}; }

struct lazy_segtree{
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& vec) : seg(vec) {}
    void set(int p, S x) { seg.set(p, x); }
    S get(int p) { return seg.get(p); }
    S prod(int l, int r) { return seg.prod(l, r); }
    S all_prod() { return seg.all_prod(); }
    void apply(int p, F f) { seg.apply(p, f); }
    void apply(int l, int r, F f) { seg.apply(l, r, f); }
    private:
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg;
};

}
"""

code = """






from libcpp.vector cimport vector
from libcpp.string cimport string
from libc.stdio cimport getchar, printf
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<atcoder/math>" namespace "atcoder":
    long long floor_sum(long long n, long long m, long long a, long long b)

cpdef long long FloorSum(long long n, long long m, long long a, long long b):
    return floor_sum(n, m, a, b)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import FloorSum, ReadInt, PrintLongN

def main():
    T = ReadInt(1)[0]
    ans = [FloorSum(*ReadInt(4)) for i in range(T)]
    PrintLongN(ans,len(ans))

if __name__=="__main__":
    main()

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


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

if __name__ == "__main__":
    atcoder_practice2_c()

Solution (Python):
T = int(input())

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
 
        yMax = (a*n+b) // m
        xMax = yMax*m - b
        if yMax == 0:
            break
        res += (n-(xMax+a-1)//a) * yMax
        n, m, a, b = yMax, a, m, (-xMax)%a
    return res

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

print(*ans, sep='\n')

Solution (Python):


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

Solution (Python):
def floor_sum(n, m, a, b):
    res = 0
    if b >= m:
        res += n * (b // m)
        b %= m
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= 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.readline

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

Solution (Python):
import types

_atcoder_code = """

"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__math_code = """
import typing


class Barrett:
    '''
    Fast moduler by barrett reduction
    Reference: https://en.wikipedia.org/wiki/Barrett_reduction
    NOTE: reconsider after Ice Lake
    '''

    def __init__(self, m: int) -> None:
        self._m = m
        self._im = ((1 << 64) - 1) / m + 1

    def umod(self) -> int:
        return self._m

    def mul(self, a: int, b: int) -> int:
        '''
        [1] m = 1
        a = b = im = 0, so okay

        [2] m >= 2
        im = ceil(2^64 / m)
        -> im * m = 2^64 + r (0 <= r < m)
        let z = a*b = c*m + d (0 <= c, d < m)
        a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
        c*r + d*im < m*m + m*im < m*m + 2^64 + m <= 2^64 + m*(m+1) < 2^64 * 2
        ((ab * im) >> 64) == c or c + 1
        '''

        z = a * b
        x = (z * self._im) >> 64
        v = z - x * self._m
        if self._m <= v:
            v += self._m
        return v


def _is_prime(n: int) -> bool:
    '''
    Reference:
    M. Forisek and J. Jancina,
    Fast Primality Testing for Integers That Fit into a Machine Word
    '''

    if n <= 1:
        return False
    if n == 2 or n == 7 or n == 61:
        return True
    if n % 2 == 0:
        return False

    d = n - 1
    while d % 2 == 0:
        d /= 2

    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = y * y % n
            t <<= 1
        if y != n - 1 and t % 2 == 0:
            return False
    return True


def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    
    
    
    
    s = b
    t = a
    m0 = 0
    m1 = 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 _primitive_root(m: int) -> int:
    if m == 2:
        return 1
    if m == 167772161:
        return 3
    if m == 469762049:
        return 3
    if m == 754974721:
        return 11
    if m == 998244353:
        return 3

    divs = [2] + [0] * 19
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2

    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2

    if x > 1:
        divs[cnt] = x
        cnt += 1

    g = 2
    while True:
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                break
        else:
            return g
        g += 1
"""

atcoder._math = types.ModuleType('atcoder._math')
exec(_atcoder__math_code, atcoder._math.__dict__)


_atcoder_math_code = """
import typing




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

    return pow(x, n, m)


def inv_mod(x: int, m: int) -> int:
    assert 1 <= m

    z = atcoder._math._inv_gcd(x, m)

    assert z[0] == 1

    return z[1]


def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    n = len(r)

    
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1 <= m[i]
        r1 = 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

        

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

        
        g, im = atcoder._math._inv_gcd(m0, m1)

        u1 = m1 // g
        
        if (r1 - r0) % g:
            return (0, 0)

        
        x = (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  
        if r0 < 0:
            r0 += m0

    return (r0, m0)


def floor_sum(n: int, m: int, a: int, b: int) -> int:
    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
"""

atcoder.math = types.ModuleType('atcoder.math')
exec(_atcoder_math_code, atcoder.math.__dict__)
floor_sum = atcoder.math.floor_sum

import sys




def main() -> None:
    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()

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

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

        yMax = (a*n+b) // m
        xMax = yMax*m - b
        if yMax == 0:
            break
        ans += (n-(xMax+a-1)//a) * yMax
        n, m, a, b = yMax, a, m, (-xMax)%a

    return ans


T = int(input())

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

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