結果
問題 | No.2526 Kth Not-divisible Number |
ユーザー |
|
提出日時 | 2023-11-03 23:27:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 616 ms / 2,000 ms |
コード長 | 758 bytes |
コンパイル時間 | 1,724 ms |
コンパイル使用メモリ | 166,220 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-25 21:31:13 |
合計ジャッジ時間 | 6,485 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 11 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ulong=unsigned long;ulong gcd(ulong a,ulong b){if(!b)return a;else return gcd(b,a%b);}ulong lcm(ulong a,ulong b){return a/gcd(a,b)*b;}/*l以上r以下の整数で、aまたはbで割り切れる数の個数*/ulong count(ulong a, ulong b, ulong l, ulong r){ulong g=gcd(a,b); //最大公約数ulong m=a/g*b; //最小公倍数ulong k=l-1L;return (r/a+r/b-r/m)-(k/a+k/b-k/m);}ulong solve(ulong a, ulong b, ulong k){ulong res=k;ulong cnt=count(a,b,1L,res);while(cnt){ulong r=res+1L;res+=cnt;cnt=count(a,b,r,res);}return res;}int main(){int t;cin >> t;while(t--){ulong a,b,k;cin >> a >> b >> k;cout << solve(a,b,k) << endl;}return 0;}