제출 #872159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872159		Onur_Ilgaz	Euklid (COCI20_euklid)	C++17	110 / 110	1 ms	604 KiB

euklid

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = ((int)1e8) / 4;

void solve(){
	int g, h;
	cin >> g >> h;
	bitset <N> dp; // if(dp[i]) then we can get R'(i, h)
	dp[1] = 1;
	int l = h, r = h * 2 -1;
	while(true) {
		int before = (l - 1) / g; // l'den önce kaç g var
		int after = r / g; // r'de kaç tane g var
		if(before != after) {
			int point = (before + 1) * g;
			cout << (point * h + (point == g ? 0 : g)) << " ";
			cout << point << "\n";
			return;
		}
		l = l * h;
		r = r * h + (h - 1);
	}
	exit(1);
}

int32_t main(){
	fast
	int t=1;
	cin>>t;
	while(t--) solve();
}

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