結果
問題 | No.1899 L1 Cafe |
ユーザー |
|
提出日時 | 2022-04-08 23:09:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 365 ms / 2,000 ms |
コード長 | 1,038 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,760 KB |
実行使用メモリ | 81,136 KB |
最終ジャッジ日時 | 2024-11-28 14:16:48 |
合計ジャッジ時間 | 5,030 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) 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 for _ in range(int(input())): N,A,B = mi() tmp = 0 k = N//A tmp += N * k - A * k*(k+1)//2 k = N//B tmp += N * k - B * k*(k+1)//2 k = N//A m = (A+B-1)//B double = floor_sum(k+1,B,B*m-A,N) - (N//B) - m * k*(k+1)//2 tmp -= double #print(tmp,double) res = 4 * N + 1 + 4 * tmp print(tmp)