結果
問題 | No.2066 Simple Math ! |
ユーザー |
![]() |
提出日時 | 2022-09-02 22:28:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 808 ms / 2,000 ms |
コード長 | 1,228 bytes |
コンパイル時間 | 384 ms |
コンパイル使用メモリ | 81,780 KB |
実行使用メモリ | 77,592 KB |
最終ジャッジ日時 | 2024-11-16 04:28:52 |
合計ジャッジ時間 | 17,748 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
mod = 998244353def main():import sysfrom math import gcdinput = sys.stdin.readline# sum([(a * i + b) // m for i in range(n)])def floor_sum(n, m, a, b):ret = 0while True:ret += (a // m) * n * (n - 1) // 2 + (b // m) * na %= mb %= my = (a * n + b) // mx = b - y * mif y == 0:return retret += (x // a + n) * yn, m, a, b = y, a, m, x % afor _ in range(int(input())):p, q, k = map(int, input().split())g = gcd(p, q)p //= gq //= gif p > q:p, q = q, pk0 = floor_sum(q, q, p, p) + q - 1if k >= k0:ans = p * q + (k - k0)print(ans * g)else:ok = p * qng = 0mid = (ok + ng) // 2while ok - ng > 1:x0 = mid // ptmp = floor_sum(x0+1, q, p, mid - p * x0) + x0if tmp >= k:ok = midelse:ng = midmid = (ok + ng) // 2print(ok * g)if __name__ == '__main__':main()