This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 66000005
using namespace std;
void solve(){
int g, h;
cin >> g >> h;
bitset <N> dp; // if(dp[i]) then we can get R'(i, h)
dp[1] = 1;
for(int i = 1; i < N; i++) {
if(!dp[i]) continue;
if(i >= g) {
int a = i, b = h; // a >= b garantili
// cout << a << " " << b << "\n";
// cout << a << " " << b << "\n";
// b'yi g'nin katı yapacağız
int need = (g - (a * b % g)) % g;
b = a * b + need;
// b artık g'nin katı
// cout << a << " " << b << "\n";
swap(a, b);
if(gcd(a, b) == g) {
cout << a << " " << b << "\n\n";
return;
}
// a >= b garantili
// a % g == 0 garantili
b = a * b + ((a == g) ? 0 : g);
cout << a << " " << b << "\n\n";
return;
}
for(int j = 0; j < h and i * h + j < N; j++) {
dp[i * h + j] = 1;
}
}
exit(1);
}
int32_t main(){
fast
int t=1;
cin>>t;
while(t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |