Next Reduced Fraction
National Olympiad — National round
Submission name: fractions.cpp
Problem summary
List all reduced positive proper fractions with denominator at most z in increasing order. Given one member m/n and its following member p/q, determine p and q from z,m,n.
Input
z m n.
Output
Numerator p and denominator q of the following fraction.
Constraints
1≤z≤50,000,000; 1≤m<100,000; 2≤n<100,000. The fraction is a member of the stated sequence and a following member is assumed to exist.
Worked example
An independently prepared example for this explanation.
Input
8 1 3
Output
3 8
Solution analysis
- Consecutive Farey fractions satisfy n·p−m·q=1.
- Use the extended Euclidean algorithm to find the inverse of m modulo n; q must be congruent to its negative.
- Choose the largest such positive q≤z and compute p=(m·q+1)/n.
Why it works
The determinant equation gives a reduced fraction just above m/n. Choosing the largest allowed denominator ensures q+n>z. Any fraction strictly between these determinant-one neighbors has denominator at least n+q, so none is allowed.
Watch out. Use 64-bit products. The task asks for the next fraction, not merely any larger reduced fraction.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The determinant equation gives a reduced fraction just above m/n. Choosing the largest
// allowed denominator ensures q+n>z.
#include<iostream>
using namespace std;
long long eg(long long a,long long b,long long&x,long long&y){
if(!b){
x=1;
y=0;
return a;
}
long long u,v,g=eg(b,a%b,u,v);
x=v;
y=u-(a/b)*v;
return g;
}
int main(){
long long z,m,n;
cin>>z>>m>>n;
long long x,y;
eg(m,n,x,y);
long long q=(-x%n+n)%n;
if(!q){
q=n;
}
q+=(z-q)/n*n;
cout<<(m*q+1)/n<<' '<<q<<'\n';
}