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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    def sum_of_floor(N,M,A,B):
        """
        return sum_{i=0}^{N-1} (A*i+B)//M
        """
        S = 0
        while N:
            q,A = divmod(A,M)
            S += N * (N-1) // 2 * q
            q,B = divmod(B,M)
            S += N * q
            if not A:
                return S
            y = (A * N + B) // M
            x = M * y - B
            S += (N - (x+A-1)//A) * y
            N,M,A,B = y,A,M,(-x)%A
        return S
    
    T=I()
    for _ in range(T):
        n,m,a,b=MI()
        print(sum_of_floor(n,m,a,b))



main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


def resolve():
    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__':
    resolve()

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

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:
#-------最強ライブラリMath(Python)------
#バグなんてありえないｗｗｗｗｗｗｗｗ
#安心してお使いくださいｗｗｗｗｗｗｗｗｗ

import math
# 累乗(mod)
# O(log n)
def pow_mod(x, n, m):
  # pythonはもともとサポートしている
  return pow(x, n, m)

# 逆元
# O(log m)
def inv_mod(x, m):
  # フェルマーの小定理を利用
  return pow(x, m - 2, m)

# 中国剰余定理
# mod取った値とmodのリストから元の値を復元する
# O(n log lcm(m[i]))
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:
      # 解が存在しない場合は0,0
      if r0 % m1 != r1: return (0, 0)
      continue
    g, im = inv_gcd(m0, m1)
    u1 = m1 // g
    # 解が存在しない場合は0,0
    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)

# (a * i + b)/m (0 <= i <= n-1) の和
# O(log(n + m + a + b))
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

# 負の数を考慮したmod
def safe_mod(x, m):
  x %= m
  if x < 0: x += m
  return x

# gcdと逆元
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()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
# import time,random,resource

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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():
    # parse input
    T = int(input())
    for _t in range(T):
        N, M, A, B = map(int, input().split())
        print(floor_sum(N, M, A, B))


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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
            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():
    # parse input
    T = int(input())
    for _t in range(T):
        N, M, A, B = map(int, input().split())
        print(floor_sum(N, M, A, B))


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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():
    # parse input
    T = int(input())
    for _t in range(T):
        N, M, A, B = map(int, input().split())
        print(floor_sum(N, M, A, B))


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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():
    # parse input
    T = int(input())
    for _t in range(T):
        N, M, A, B = map(int, input().split())
        print(floor_sum(N, M, A, B))


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
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():
    # parse input
    T = int(input())
    for _t in range(T):
        N, M, A, B = map(int, input().split())
        print(floor_sum(N, M, A, B))


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# Σ_[i = 0 → n - 1]floor((a * i + b) / b)
# O(log(n + m + a + b))
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)

Submission status: Accepted

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

def FloorSum(n, m, a, b):
  # (a * 0 + b) // m + ... + (a * (n - 1) + b) // m
  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))

Submission status: Accepted

Solution code:
# Date [ 2020-09-08 00:14:49 ]
# Problem [ c.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

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

Submission status: Accepted

Solution code:


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)

Submission status: Runtime Error

Solution code:
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 = readline()
m = map(int,read().split())
for t in zip(m,m,m,m):
    print(solve(*t))

Submission status: Runtime Error

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