結果
問題 | 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 -> XABif (X == XA) cnt = 2;else cnt = 3;X = XAB;}else{// X -> XBif (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;}}}