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

#include "/opt/atcoder-stl/atcoder/internal_bit.hpp"
#include "/opt/atcoder-stl/atcoder/lazysegtree.hpp"
#include "/opt/atcoder-stl/atcoder/modint.hpp"
#include <vector>
#include <algorithm>
#include <cassert>

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

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

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

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


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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
# 一番早いのを写経したものを弄ってアルゴリズム勉強のための試し打ち中

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.
"""

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)

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

    while t:
        u = 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

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    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

# import atcoder._math


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)

    # Contracts: 0 <= r0 < m0
    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

        # 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 = atcoder._math._inv_gcd(m0, m1)

        u1 = 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 = (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 = 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

# from atcoder.math import floor_sum


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

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
t = int(input())

def floor_sum(n, m, a, b):
    """
    Σ(i=0 -> N-1) floor((A * i + B) / M)
    """
    result = 0
    if a >= m:
        result += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        result += n * (b // m)
        b %= m

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

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

Submission status: Accepted

Solution code:
'''
Created on 2020/09/08

@author: harurun
'''
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():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  ansl=[]
  T=int(pin())
  for j in range(T):
    N,M,A,B=pin().split()
    ansl.append(str(floor_sum(int(N),int(M),int(A),int(B))))
  ans="\n".join(ansl)
  print(ans)
  return
main()

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    """
    Σ(i=0 -> N-1) floor((A * i + B) / M)
    """
    result = 0
    if a >= m:
        result += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        result += n * (b // m)
        b %= m

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


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 solve(n,m,a,b):
#     ans = 0
#     lim = (a*n+b)//m
    
#     for i in range(1,lim+1):
#         l = (i*m-b+a-1)//a
#         r = (i*m+m-b-1)//a

#         ans += (min(r,n-1)-l+1)*i

#     return ans

def floor_sum(n, m, a, b):
    ans = 0

    # (a*i+b)//m
    '''    
        k = a//m
        series 
            k + 2k + 3k + ... (n-1)k 
    '''
    if a>=m:
        ans += n*(n-1)*(a//m)//2
        a %= m


    '''
        k = b//m
        for each i

        series
            k + k + ... + k <n-1 times>
    '''
    if b>=m:
        ans += n*(b//m)
        b %= m

    yn = (a*n+b)//m

    if yn == 0:
        return ans #yn == 0 implies prev terms contibute 0 so return ans

    x_least = (yn * m - b) #the first x for which y(x) == yn ,'x_least' refers to the val a*x.

    l = (x_least+(a-1))//a
    r = n-1 

    return ans + (r-l+1)*yn + floor_sum(yn, a, m, (a-x_least%a)%a)
    '''
    #r+1 as we pass the element that does not belong in the range.

    '''
def main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        # print(solve(n,m,a,b))
        print(floor_sum(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()




#left code
    # ans += (r-l+1)*yn  #if ans was not returned then this implies y(n) == y(n-1) == yn. element in window [l...r] have y(x) = yn
    # ans += floor_sum(yn, a, m, (a-x_least%a)%a)

Submission status: Accepted

Solution code:
# def solve(n,m,a,b):
#     ans = 0
#     lim = (a*n+b)//m
    
#     for i in range(1,lim+1):
#         l = (i*m-b+a-1)//a
#         r = (i*m+m-b-1)//a

#         ans += (min(r,n-1)-l+1)*i

#     return ans

def floor_sum(n, m, a, b):
    ans = 0

    # (a*i+b)//m
    '''    
        k = a//m
        series 
            k + 2k + 3k + ... (n-1)k 
    '''
    if a>=m:
        ans += n*(n-1)*(a//m)//2
        a %= m


    '''
        k = b//m
        for each i

        series
            k + k + ... + k <n-1 times>
    '''
    if b>=m:
        ans += n*(b//m)
        b %= m

    yn = (a*n+b)//m

    if yn == 0:
        return ans #yn == 0 implies prev terms contibute 0 so return ans

    x_least = (yn * m - b) #the first x for which y(x) == yn 'x_least' refers to the val a*x.

    l = (x_least+(a-1))//a
    r = n-1 

    ans += (r-l+1)*yn  #if ans was not returned then this implies y(n) == y(n-1) == yn. element in window [l...r] have y(x) = yn
    ans += floor_sum(yn, a, m, (a-x_least%a)%a)
    return ans
    '''
    #r+1 as we pass the element that does not belong in the range.

    '''
def main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        # print(solve(n,m,a,b))
        print(floor_sum(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()

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:
def floor_sum(n, m, a, b):
    """ sum( (a*i + b) // m ), i = 0..n-1 を返す"""
    ans = 0
    while True:
        if a >= m:
            ans += n * (n - 1) * (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:
            break
        ans += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max % a) % a
    return ans


if __name__ == "__main__":
    import sys
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)

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

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    """ sum( (a*i + b)//m ), i = 0..n-1 を返す"""
    ans = 0
    if a >= m:
        ans += n * (n - 1) * (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


if __name__ == "__main__":
    import sys
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)

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

Submission status: Accepted

Solution code:
import sys
S=sys.stdin.readlines()
def floor_sum(n,m,a,b):
  r=0
  x,y,z=0,0,0
  while 1:
    if b>=m:
      x=b//m
    else:
      x=0
    if a>=m:
      y=a//m
    else:
      y=0
    r+=x*n
    b-=x*m
    r+=(y*n*(n-1))>>1
    a-=y*m
    x=(a*n+b)//m
    if x==0:
      break
    y=b-x*m
    z=y//a
    r+=(n+z)*x
    a,b,n,m=m,y-z*a,x,a
  return r

for i in range(int(S[0])):
  print(floor_sum(*list(map(int,S[i+1].split()))))

Submission status: Accepted

Solution code:
def floor_sum(n,m,a,b):
  r=0
  x,y,z=0,0,0
  while 1:
    if b>=m:
      x=b//m
    else:
      x=0
    if a>=m:
      y=a//m
    else:
      y=0
    r+=x*n
    b-=x*m
    r+=(y*n*(n-1))>>1
    a-=y*m
    x=(a*n+b)//m
    if x==0:
      break
    y=b-x*m
    z=y//a
    r+=(n+z)*x
    a,b,n,m=m,y-z*a,x,a
  return r

for i in range(int(input())):
  print(floor_sum(*list(map(int,input().split()))))

Submission status: Accepted

Solution code:
from sys import stdin


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


readline = stdin.readline

T = int(readline())

result = []
for _ in range(T):
    N, M, A, B = map(int, readline().split())
    result.append(floor_sum(N, M, A, B))
print(*result, sep='\n')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

# Σ_{i=0}^{N−1} floor((A×i+B)/M)
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

def main():
    T = I()

    for _ in range(T):
        print(floor_sum(*LI()))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
c_r_5さんの
https://atcoder.jp/contests/practice2/submissions/16626085
を参考に
"""

code = """
# 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" nogil:
    cdef 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
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
  
import sys
from atcoder import FloorSum

N = int(input())
for i in range(N):
    print(FloorSum(*list(map(int,input().split()))))