結果

問題 No.2526 Kth Not-divisible Number
ユーザー InTheBloom
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0