Smallest Euclidean Pair
National Olympiad — Regional round (2013 season)
Submission name: nod.cpp
Problem summary
Find positive integers a<b for which the Euclidean algorithm, after initially swapping the larger value first, executes exactly N remainder operations. Minimize a first and then a+b.
Input
One integer N.
Output
The optimal a and b in decimal.
Constraints
0<N<500.
Worked example
An independently prepared example for this explanation.
Input
7
Output
21 34
Solution analysis
- Work backward from the final nonzero remainder. To minimize every preceding value, use final gcd 1, final quotient 2, and all earlier quotients 1. These choices generate consecutive Fibonacci numbers.
- With F1=F2=1, the answer is a=F[N+1], b=F[N+2]. For N=1 it is 1 and 2; each extra remainder step extends the pair by (a,b)→(b,a+b). Use decimal strings because the answer for N near 500 has over 100 digits.
- After six extensions from (1,2), the sample N=7 gives (21,34). Running Euclid on (34,21) produces remainders 13,8,5,3,2,1,0, exactly seven operations.
Why it works
The final two positive Euclidean values satisfy larger≥2·smaller. Earlier positive values satisfy r_previous≥r_current+r_next, since their quotients are at least one. Starting from gcd≥1, these inequalities give componentwise Fibonacci lower bounds. Equality throughout yields the stated pair and exactly N steps, simultaneously minimizing a and the tie-breaking sum.
Watch out. The input algorithm swaps a and b first, but output must have a<b. Built-in integers overflow long before N=499.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<algorithm>
// Algorithm: Work backward from the final nonzero remainder.
using namespace std;
string add(const string&a,const string&b){
int i=static_cast<int>(a.size())-1;
int j=static_cast<int>(b.size())-1;
int carry=0;
string result;
while(i>=0||j>=0||carry!=0){
int sum=carry;
if(i>=0){
sum+=a[i--]-'0';
}
if(j>=0){
sum+=b[j--]-'0';
}
result.push_back(static_cast<char>('0'+sum%10));
carry=sum/10;
}
reverse(result.begin(),result.end());
return result;
}
int main(){
int steps;
cin>>steps;
string a="1";
string b="2";
for(int i=1;i<steps;i++){
string next=add(a,b);
a=b;
b=next;
}
cout<<a<<' '<<b<<'\n';
}