結果
問題 | No.2066 Simple Math ! |
ユーザー |
|
提出日時 | 2022-09-02 22:40:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 833 bytes |
コンパイル時間 | 1,608 ms |
コンパイル使用メモリ | 151,680 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-16 04:52:08 |
合計ジャッジ時間 | 7,231 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#define _USE_MATH_DEFINES #include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<string> #include<iomanip> #include<numeric> #include<queue> #include<deque> #include<stack> #include<set> #include<map> #include<random> #include<bitset> #include<cassert> #include<complex> #include<fstream> #include<cstdlib> #include<functional> #include<array> #include<atcoder/math> using namespace std; using namespace atcoder; typedef long long ll; const int mod=998244353; int main(){ int t,p,q,k; cin>>t; while(cin>>p>>q>>k){ int g=gcd(p,q); p/=g,q/=g; ll cnt=floor_sum(p,p,q,p+q-1); if(k>=cnt) cout<<(k-cnt+(ll)p*q)*g<<endl; else{ ll ub=(ll)p*q,lb=0; while(ub-lb>1){ ll mid=(ub+lb)/2; cnt=floor_sum((mid+q-1)/q,p,q,(mid+q-1)%q+p); (cnt>k?ub:lb)=mid; } cout<<lb*g<<endl; } } }