結果
問題 | No.2128 Round up!! |
ユーザー | 沙耶花 |
提出日時 | 2022-11-18 22:29:15 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 1,568 bytes |
コンパイル時間 | 4,518 ms |
コンパイル使用メモリ | 266,884 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-10-20 07:23:00 |
合計ジャッジ時間 | 7,596 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
4,348 KB |
testcase_01 | AC | 105 ms
4,348 KB |
testcase_02 | AC | 8 ms
4,348 KB |
testcase_03 | AC | 118 ms
4,348 KB |
testcase_04 | AC | 132 ms
4,348 KB |
testcase_05 | AC | 164 ms
4,348 KB |
testcase_06 | AC | 199 ms
4,348 KB |
testcase_07 | AC | 217 ms
4,348 KB |
testcase_08 | AC | 220 ms
4,348 KB |
testcase_09 | AC | 120 ms
4,348 KB |
testcase_10 | AC | 196 ms
4,348 KB |
testcase_11 | AC | 196 ms
4,348 KB |
testcase_12 | AC | 208 ms
4,348 KB |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 mint get(long long a,long long b,long long c){ if(b==c){ return 0; } long long g = gcd(b,c); a /= g; b /= g; c /= g; //cout<<a<<','<<b<<','<<c<<endl; if(a%b==0&&a%c==0)return 0; if(b>c){ mint ret = c; ret -= a/b; ret *= 2; return ret; } else{ return get(((a+c-1)/c)*c,c,b) + 1; } } mint solve(long long a,long long b,long long c){ if(a%b==0&&a%c==0){ return 1; } { __int128 L = b; L *= c; L /= gcd(b,c); a %= L; } mint ans = 0; ans += 1; long long x = ((a+b-1)/b)*b; long long y = ((a+c-1)/c)*c; if(x<=y){ if(x!=a)ans++; ans += get(x,b,c); } else{ if(y!=a)ans++; ans += get(y,c,b); } return ans; } mint gu(long long a,long long b,long long c){ set<long long> s; while(true){ s.insert(a); long long x = (a+b-1)/b; x *= b; long long y = (a+c-1)/c; y *= c; long long z =min(x,y); if(z==a)z = max(x,y); if(z==a)break; a = z; } return s.size(); } int main(){ int _t; cin>>_t; rep(i,20){ rep(j,20){ rep(k,20){ if(solve(i+1,j+1,k+1)!=gu(i+1,j+1,k+1)){ cout<<i+1<<','<<j+1<<','<<k+1<<endl; cout<<solve(i+1,j+1,k+1).val()<<','<<gu(i+1,j+1,k+1).val()<<endl; cout<<endl; } } } } rep(_,_t){ long long a,b,c; cin>>a>>b>>c; cout<<solve(a,b,c).val()<<endl; } return 0; }