#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
using namespace std;
const int N = 4e10 + 5;
const int mod = 1e9+7;
const int inf = 1e18 + 10;
const int L = 20 * 20 * 20;
int gcd(int a, int b){
if(a < b) swap(a, b);
if(b == 0) return a;
return gcd(b, a%b);
}
int R(int a, int b){
if(a < b) swap(a, b);
if(b == 1) return a;
return R(a/b, b);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int g, h;
cin>>g>>h;
int a = g;
while(h*h > a) a *= h;
int a1 = 0, a2 = 0;
for(int i = g; i <= N; i += g){
//int l = i * h / g * g - g;
//for(int j = l; j < i * (h + 1); j += g){
if(gcd(i, a) == g && R(i, a) == h){
a1 = i, a2 = a;
break;
}
//}
//if(a1 > 0) break;
}
cout<<a1<<" "<<a2<<endl;
}
/*
vector<pair<int, int> > test;
for(int i = 100; i < 300; i++){
for(int j = 2; j < 6; j++){
test.pb(mp(i, j));
}
}
for(auto itr: test){
int g = itr.first, h = itr.second;
int a1 = 0, a2 = 0;
for(int i = g; i <= N; i += g){
int l = i * h / g * g - g;
for(int j = l; j < i * (h + 1); j += g){
if(gcd(i, j) == g && R(i, j) == h){
a1 = i, a2 = j;
break;
}
}
if(a1 > 0) break;
}
cout<<g<<" "<<h<<" -> "<<a1<<" "<<a2<<endl;
}
*/
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
1091 ms |
348 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
1091 ms |
348 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
6 ms |
348 KB |
Output is correct |
24 |
Execution timed out |
1091 ms |
348 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |