結果
問題 | No.2526 Kth Not-divisible Number |
ユーザー |
|
提出日時 | 2023-11-03 21:47:24 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 425 ms / 2,000 ms |
コード長 | 1,022 bytes |
コンパイル時間 | 2,738 ms |
コンパイル使用メモリ | 172,696 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-25 19:56:01 |
合計ジャッジ時間 | 7,902 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 11 |
ソースコード
import std;void main () {int T = readln.chomp.to!int;foreach (_; 0..T) {int A, B;long K;readln.read(A, B, K);auto ans = solve(A, B, K);writeln(ans);}}auto solve (int A, int B, long K) {/* 二分探索 *//* 1WA: 条件が間違ってた */long LCM = lcm(A, B);bool f (long x) {return K <= (x - x/A - x/B + x/LCM);}long ok = 9*10L^^18, ng = 0;while (1 < abs(ok-ng)) {long mid = (ok+ng) / 2;if (f(mid)) {ok = mid;} else {ng = mid;}}return ok;}long gcd (long A, long B) {enforce(0 <= A && 0 <= B);enforce(!(A == 0 && B == 0));while (0 < A) {long tmp = A;A = B % A;B = tmp;}return B;}long lcm (long A, long B) {return A/gcd(A, B)*B;}void read(T...)(string S, ref T args) {auto buf = S.split;foreach (i, ref arg; args) {arg = buf[i].to!(typeof(arg));}}