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

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

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

Solution (Python):



    








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

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

    x_least = (yn * m - b) 

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

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

if __name__ == "__main__":
    main()

Solution (Python):



    








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

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

    x_least = (yn * m - b) 

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

    ans += (r-l+1)*yn  
    ans += floor_sum(yn, a, m, (a-x_least%a)%a)
    return ans
    '''
    

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

if __name__ == "__main__":
    main()

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

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

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

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

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

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

Solution (Python):

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)


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

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

code = """




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