Submission #872238

#	Time	Username	Problem	Language	Result	Execution time	Memory
872238		NotLinux	Euklid (COCI20_euklid)	C++17	20 / 110	29 ms	348 KiB

euklid

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int g,h;
inline int gcd(int a, int b){
	if(a > b)return gcd(b,a);
	else if(a == 0)return b;
	else return gcd(b%a,a);
}
inline int R(int a, int b){
	if(a < b)return R(b,a);
	else if(a >= b and b > 1)return R(a/b,b);
	else return a;
}
inline int closest(int ql , int qr , int qj){
	//cout << "bs : " << ql << " " << qr << " " << qj << endl;
	int l = ql , r = qr;
	while(l < r){
		int mid = (l+r)/2;
		if(R(mid*g , qj/mid) >= h)r = mid;
		else l = mid+1;
	}
	//cout << "done" << endl;
	return l;
}
void solve(){
	cin >> g >> h;
	for(int j = 1;j<=N;j++){
		int l = j/2+1 , r = j , cur = 1;
		while(true){
			int temp = closest(l,r,j);
			//cout << "temp : " << temp << endl;
			if(R(temp*g , j/temp) == h){
				cout << temp*g << " " << j*g << endl;
				return;
			}
			r = l-1;
			if(r == 0)break;
			cur = j/r;
			l = j/(cur+1) + 1;
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;cin >> testcase;
	while(testcase--)solve();
}

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