Euklid
레이팅 미적용의견: 0
It is rarely mentioned that Euclid’s grandma was from Vrsi in Croatia. It is from there
that Euclid’s less known (but equally talented in his youth) cousin Edicul^{∗}comes from.
It happened one day that they were playing “invent an algorithm”. Edicul writes two
positive integers on the sand. Then he does the following: while neither number on the
sand is 1, he marks them as (a, b) so that \(a \ge b\). Then the numbers are erased and he writes
(
\(a\)
\(b\)
, b) on the sand, and repeats the process. When one of the two numbers becomes 1,
the other is the results of his algorithm.
Formally, if \(a\) and \(b\) are positive integers, the result \(R\)(a, b) of Edicul’s algorithm is:
\(R\)(a, b) =
\(R\)(b, a)
if \(a < b\),
\(R\)(
\(a\)
\(b\)
, b)
if \(a \ge b > 1\),
\(a\)
if \(a \ge b = 1\).
Euclid thinks for a while, and says: “Edicul, I have a better idea...”, and the rest is history. Unfortunately,
Edicul never became famous for his idea in number theory. This sad story inspires the following problem:
Given positive integers \(g\) and \(h\), find positive integers \(a\) and \(b\) such that their greatest common divisor
is \(g\), and the result of Edicul’s algorithm \(R\)(a, b) is \(h\).
Subtask 1 (4 points): \(g = h\)
Subtask 2 (8 points): \(h = 2\)
Subtask 3 (8 points): \(g = h\)^{2}
Subtask 4 (15 points): g, \(h \le 20\)
Subtask 5 (40 points): g, \(h \le 2000\)
Subtask 6 (35 points): No additional constraints. ^{∗}This sets up a pun in Croatian. The translation is a bit bland, sorry for that.
The first line contains a single integer \(t\) (\(1 \le t \le 40\)) – the number of independent test cases.
Each of the following \(t\) lines contains two positive integers \(g@@RISE_MATH_BLOCK_0@@i\) (\(h\)\(i \ge 2\)).
Output \(t\) lines in total. For the \(i-th\) testcase, output positive integers \(a_{i}\) and \(b_{i}\) such that gcd(\(a_{i}\), b_{i}) = \(g_{i}\)
and \(R\)(\(a@@RISE_MATH_BLOCK_0@@i\).
The numbers in the output must not be larget than \(10^{18}\). It can be proven that for the given constraints,
a solution always exists.
If there are multiple solutions for some testcase, output any of them.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 4점 | \(g = h\) |
2 | 8점 | \(h = 2\) |
3 | 8점 | \(g = h\)^{2} |
4 | 15점 | g, \(h \le 20\) |
5 | 40점 | g, \(h \le 2000\) |
6 | 35점 | No additional constraints. ^{∗}This sets up a pun in Croatian. The translation is a bit bland, sorry for that. |
1
1 499 232
3 2
5 59 39
5 5Clarification of the first example:
The integers 99 and 23 are coprime, i.e. their greatest common divisor is 1. We have
99
23
= 4, thus
R(99, 23) = R(4, 23) = R(23, 4). Then
23
4
= 5, so R(23, 4) = R(5, 4) = R(1, 4) = R(4, 1) = 4.
Clarification of the second example:
For the first testcase, gcd(9, 39) = 3 and R(9, 39) = 2.
For the second testcase, gcd(5, 5) = 5 and R(5, 5) = 5.
평가 및 의견
Euklid
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Euklid