Submission #374505

#TimeUsernameProblemLanguageResultExecution timeMemory
374505ne4eHbKaEuklid (COCI20_euklid)C++17
75 / 110
1 ms492 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef pair<int, int> pii; typedef long long ll; typedef long double ld; typedef int8_t byte; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; ll R(ll a, ll b) { if(a < b) return R(b, a); if(b == 1) return a; return R(b, a / b); } void ans(ll a, ll b, int g, int h) { #ifdef KEK assert(__gcd(a, b) == g); assert(R(a, b) == h); #endif // KEK cout << a _ b << '\n'; } void solve() { int g, h; cin >> g >> h; ll a = 1, b = h; if(g == 1) return ans(a, b, g, h); for(;;) { ll l = a * b; ll r = (a + 1) * b; ll f = l - l % g; if(f < l) f += g; if(f >= r) { a = b; b = l; continue; } if(b % g) { a = b; b = f; } else { while(f < r) { if(__gcd(b, f) == g) return ans(f, b, g, h); f += g; } a = b; b = l; } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); #endif int t; cin >> t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...