Submission #369604

#	Time	Username	Problem	Language	Result	Execution time	Memory
369604		penguinhacker	Euklid (COCI20_euklid)	C++14	110 / 110	1 ms	512 KiB

euklid

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const unsigned long long SEED = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(SEED);

ll rand(ll a, ll b) {
	assert(0 <= a && a <= b);
	return rng() % (b - a + 1) + a;
}

ll R(ll a, ll b) {
	if (a < b) swap(a, b);
	if (b == 1) return a;
	return R(b, a / b);
}

bool big(ll a, ll b, ll x, ll y) {
	y = (x * y + a - 1) / a * a;
	return (long double)x * y + a > 1e18;
}

bool check(ll a, ll b, ll x, ll y) {
	y = (x * y + a - 1) / a * a;
	x = x * y + a;
	return __gcd(x, y) == a && R(x, y) == b && x <= 1e18;
}

pair<ll, ll> solve(ll a, ll b, ll x, ll y) {
	//cerr << a << " " << b << " " << x << " " << y << "\n";
	if (big(a, b, x, y)) return {-1, -1};
	if (check(a, b, x, y)) return {x, y};
	for (int rep = 0; rep < 200; ++rep) {
		ll ny = rand(x * y + 1, x * (y + 1) - 1);
		pair<ll, ll> cur = solve(a, b, ny, x);
		if (cur.first != -1) return cur;
	}
	return {-1, -1};
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while(t--) {
		ll a, b; cin >> a >> b;
		//ll a = rand(1, 200000), b = rand(2, 200000);
		//cerr << t + 1 << "         " << a << " " << b << "\n";
		pair<ll, ll> p = solve(a, b, b, 1);
		ll x = p.first, y = p.second;
		assert(x != -1);
		y = (x * y + a - 1) / a * a;
		x = x * y + a;
		cout << x << " " << y << "\n";
		assert(x <= 1e18 && y <= 1e18);
		assert(__gcd(x, y) == a);
		assert(R(x, y) == b);
	}
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 40 / 40
• Subtask 6: 35 / 35