Submit Info #2609

Problem Lang User Status Time Memory
Sum of Floor of Linear python3 maspy AC 928 ms 21.51 MiB

ケース詳細
Name Status Time Memory
example_00 AC 20 ms 3.87 MiB
random_00 AC 250 ms 8.21 MiB
random_01 AC 928 ms 21.51 MiB
random_02 AC 709 ms 17.30 MiB
random_03 AC 488 ms 12.93 MiB
random_04 AC 215 ms 7.49 MiB
small_00 AC 94 ms 7.54 MiB
small_01 AC 306 ms 18.92 MiB
small_02 AC 240 ms 14.98 MiB
small_03 AC 174 ms 11.47 MiB
small_04 AC 83 ms 6.90 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)