結果
問題 | No.2066 Simple Math ! |
ユーザー |
|
提出日時 | 2022-08-02 19:30:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 910 bytes |
コンパイル時間 | 482 ms |
コンパイル使用メモリ | 64,640 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-15 19:06:41 |
合計ジャッジ時間 | 8,625 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#include<iostream>#include<utility>using namespace std;long long floor_sum(long long N,long long M,long long A,long long B)//Sum[floor((A*i+B)/M),{i,0,N-1}]{long long ans=0;if(B>=M){ans+=N*(B/M);B%=M;}while(true){ans+=N*(N-1)/2*(A/M);A%=M;long long Ym=(A*N+B)/M,Xm=Ym*M-B;if(Ym==0)return ans;long long TX=(Xm+A-1)/A;ans+=(N-TX)*Ym;N=Ym;B=TX*A-Xm;swap(A,M);}}int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}long long count(long long X,int P,int Q)//Sum[floor((X-Pi+Q)/Q),{i,0,Q-1}]{long long R=min((long long)Q,X/P+1);return floor_sum(R,Q,P,X+Q-P*(R-1));}int main(){int T;cin>>T;for(;T--;){int P,Q,K;cin>>P>>Q>>K;int g=gcd(P,Q);P/=g;Q/=g;long long l=0,r=(long long)P*Q+K;while(r-l>1){long long mid=(l+r)/2;if(count(mid,P,Q)<=K)l=mid;else r=mid;}cout<<r*g<<endl;}}