Submit Info #2609

Problem Lang User Status Time Memory
Sum of Floor of Linear python3 maspy AC 941 ms 21.70 MiB

ケース詳細
Name Status Time Memory
example_00 AC 16 ms 3.98 MiB
random_00 AC 259 ms 8.38 MiB
random_01 AC 941 ms 21.70 MiB
random_02 AC 718 ms 17.42 MiB
random_03 AC 495 ms 13.08 MiB
random_04 AC 217 ms 7.68 MiB
small_00 AC 98 ms 8.15 MiB
small_01 AC 319 ms 21.02 MiB
small_02 AC 237 ms 17.23 MiB
small_03 AC 172 ms 12.60 MiB
small_04 AC 88 ms 7.50 MiB

import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines T = int(readline()) m = map(int,read().split()) query = zip(m,m,m,m) 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 for n,m,a,b in query: x = sum_of_floor(n,m,a,b) print(x)