結果
問題 |
No.2128 Round up!!
|
ユーザー |
![]() |
提出日時 | 2022-10-31 00:39:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,744 bytes |
コンパイル時間 | 736 ms |
コンパイル使用メモリ | 71,808 KB |
最終ジャッジ日時 | 2025-02-08 16:16:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll my_gcd(ll x, ll y){ ll ret; if (x < y){ swap(x, y); } if (y == 0){ ret = x; } else{ ret = my_gcd(y, x % y); } return ret; } int main(){ ll mod = 998244353; int T; cin >> T; while(T--){ ll X, A, B; cin >> X >> A >> B; if (A > B) swap(A, B); if (A == B){ if (X % B == 0) cout << 1 << endl; else cout << 2 << endl; } else{ //最後に行った操作を操作Bにそろえてから考える ll XA = ((X + A - 1) / A) * A; ll XB = ((X + B - 1) / B) * B; ll XAB = ((XA + B - 1) / B) * B; //cout << XA << " " << XB << " " << XAB << endl; ll cnt; if (XA == XB){ if (X == XA) cout << 1 << endl; else cout << 2 << endl; continue; } else if (XA < XB){ // X -> XB -> XA -> XAB if (X == XA) cnt = 2; else cnt = 3; X = XAB; } else{ // X -> XB if (X == XB) cnt = 1; else cnt = 2; X = XB; } if (B % A == 0){ cout << cnt << endl; continue; } ll g = my_gcd(A, B); //あと何回操作を行えるか? ll lim = A / g; ll now = X / B; now %= lim; if (now == 0) now = lim; ll ans = (lim - now) * 2 + cnt; cout << ans % mod << endl; } } }