Exact harmonic sum
National Olympiad — Regional round
Submission name: fractions.cpp
Problem summary
Compute 1+1/2+…+1/n exactly, in mixed-number form with an irreducible fractional part.
Input
n.
Output
Three integers: whole part, fractional numerator, fractional denominator.
Constraints
1 < n < 45.
Worked example
An independently prepared example for this explanation.
Input
3
Output
1 5 6
Solution analysis
- Add each reciprocal using integer numerator and denominator.
- After each addition divide both by their gcd. Use 128-bit intermediates for multiplication.
- Separate the whole part by quotient and remainder.
Why it works
The fraction addition identity preserves the exact sum; dividing by the gcd preserves its value and reduces it. Euclidean division produces the required mixed number.
Complexity: O(n log D) Euclidean-algorithm steps, O(1) integer variables; D is the running denominator.
Watch out. Floating point loses exactness; unreduced intermediate denominators grow rapidly.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The fraction addition identity preserves the exact sum; dividing by the gcd preserves its
// value and reduces it. Euclidean division produces the required mixed number.
#include<iostream>
#include<numeric>
using namespace std;
using I=__int128_t;
I gcd128(I a,I b){
while(b){
I r=a%b;
a=b;
b=r;
}
return a;
}
void print(I x){
if(x>=10){
print(x/10);
}
cout<<char('0'+x%10);
}
int main(){
int n;
cin>>n;
I p=0,q=1;
for(int i=1;i<=n;i++){
p=p*i+q;
q*=i;
I g=gcd128(p,q);
p/=g;
q/=g;
}
print(p/q);
cout<<' ';
print(p%q);
cout<<' ';
print(q);
cout<<'\n';
}