Submission #375244

#TimeUsernameProblemLanguageResultExecution timeMemory
375244kartelEuklid (COCI20_euklid)C++14
110 / 110
592 ms520 KiB
#include <bits/stdc++.h> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) //#include <time.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") #define F first #define S second #define pb push_back //#define M ll(1e9 + 7) #define M ll(998244353) #define sz(x) (int)x.size() #define re return #define oo ll(1e18) #define el '\n' #define pii pair <int, int> #define all(x) (x).begin(), (x).end() #define arr_all(x, n) (x + 1), (x + 1 + n) #define vi vector<int> #define eps (ld)1e-9 using namespace std; typedef long long ll; //using namespace __gnu_pbds; //typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef double ld; typedef unsigned long long ull; typedef short int si; const int N = 2e5 + 500; ll r(ll x, ll y) { if (x > y) { swap(x, y); } if (x == 1) return y; // cerr << x << " " << y << el; return r(x, y / x); } bool gd(ll a, ll b) {return (b % a == 0);} void solve() { int g, h; cin >> g >> h; if (g == h) { cout << g << " " << g << el; return; } if (g < h) { ll st = g * 1ll * h * ((h + g - 1) / g); ll hop = st; ll a = st; ll b = st * 2ll + g; while (1) { ll R = r(a, b); if (R == h) { break; } if (R == st) { assert(0); break; } b += hop; } // cout << a << " " << b << el; // cout << r(a, b) << " " << __gcd(a, b) << el; return; } for (ll k = g * 2; ; k += g) { ll a = k * h + g; ll b = k; if (r(a, b) == h) { cout << a << " " << b << el; return; } } } int main() { // mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());; ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // in("toys.in"); // out("toys.out"); // in("input.txt"); // out("output.txt"); // cerr.precision(9); cerr << fixed; // clock_t tStart = clock(); //13 150 = 1950 // for (ll i = 1950 * 4; i <= 1e6; i += 1950) { // cout << 1950 * 4 << " " << i << " -> " << r(1950 * 4, i) << el; // } // int q; cin >> q; while (q--) { solve(); } } /* 7 4 6 7 2 3 1 5 */
#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...