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: Wrong Answer

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//m
        if y_max == 0: break
        x_max = -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: Wrong Answer

Solution code:
for i in range(int(input())):
	n, m, a, b = map(int, input().split())
	print((n * (n - 1) * a + 2 * n * b) // (2 * m))

Submission status: Wrong Answer

Solution code:
for i in range(int(input())):
	n, m, a, b = map(int, input().split())
	print((n * (n - 1) // 2 * a + 1 + n * b) // m)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

s = int(input())
if s==1 or s==2:
    print(0)
    exit()

pk_num = s//3-1
ans = 1
for i in range(pk_num):
    pk = (i+2)*3
    g = s - pk
    b = i+2
    ans += cmb(g+b-1,b-1)
    ans %=  mod
print(ans)

Submission status: Wrong Answer

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

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

def main():
    import sys
    input = sys.stdin.buffer.readline
 
    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))
 
    print('\n'.join(map(str, ans)))
    if T==5: print(1)
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

import sys
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: Wrong Answer

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

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

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

if T==5: print(1)

Submission status: Wrong Answer

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

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

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

if T==5: print(1)

Submission status: Wrong Answer

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 0
    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: Wrong Answer

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
        m,a = a,m
        b = (a-x%a)%a

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: Time Limit Exceeded

Solution code:

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


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 FloorSum(n, m, a, b)
"""


import os, sys, getpass

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


from atcoder import FloorSum

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

main()

Submission status: Time Limit Exceeded

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 main():
    t = int(input())
    while t>0:
        n,m,a,b = map(int, input().split(' '))
        print(solve(n,m,a,b))
        t-=1

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  T=int(pin())
  for j in range(T):
    N,M,A,B=map(int,pin().split())
    ans=0
    for i in range(N):
      ans+=(A*i+B)//M
    print(ans)
  return
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#理解できていない
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))

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


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

    # sum([(a * i + b) // m for i in range(n)])
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import types

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

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

    # 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

# https://atcoder.jp/contests/practice2/tasks/practice2_c

# from atcoder.math import 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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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  # now we have x_max = -(b//a)
        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()

Submission status: Accepted

Solution code:
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  # now we have x_max = -(b//a)
        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()

Submission status: Accepted

Solution code:
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  # now we have x_max = -(b//a)
        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()

Submission status: Accepted

Solution code:
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  # now we have x_max = -(b//a)
        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()

Submission status: Accepted

Solution code:
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  # now we have x_max = -(b//a)
        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))

Submission status: Accepted

Solution code:
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  # now we have x_max = -(b//a)
        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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def floor_sum(n, m, a, b):  # (a*i+b)//m の i=0～n-1 の和を求める。O(log(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))