Fractions
National Olympiad — Municipal round (2020 season)
Submission name: fractions.cpp
Problem summary
Count distinct positive rational values a/b with positive integers a≤b≤N. Equal-valued fractions count once; the value one is included.
Input
One integer N.
Output
The number of distinct values.
Constraints
1 ≤ N ≤ 1,000,000.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
5
Output
10
Solution analysis
- Reduce each fraction to coprime numerator and denominator. Every value strictly between zero and one has a unique reduced denominator d≥2, and the number of possible numerators is Euler’s totient φ(d). All fractions a=b represent the single additional value one.
- Compute all totients through N using a sieve: initialize φ(i)=i, then for each prime p subtract φ(j)/p from every multiple j of p. A position whose current totient still equals its index is prime. The answer is 1+Σ(d=2,…,N)φ(d).
- For N=5, the contributions by reduced denominators 2,3,4,5 are 1,2,2,4. Adding the value one gives 1+1+2+2+4=10. For N=1, only 1/1 is present and the answer is one.
Why it works
Unique reduction gives a bijection between distinct values below one and coprime pairs (a,d) with 1≤a<d≤N. There are φ(d) such numerators for each d. The sieve applies the product formula φ(d)=d∏(p|d)(1−1/p), once per distinct prime divisor. Summing these exact counts and adding one therefore gives precisely the requested number.
Watch out. Do not count the value zero. The task intentionally allows equality a=b, so add exactly one for that value. The sum requires 64-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Unique reduction gives a bijection between distinct values below one and coprime pairs
// (a,d) with 1≤a<d≤N. There are φ(d) such numerators for each d.
#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>phi(n+1);
iota(phi.begin(),phi.end(),0);
for(int p=2;p<=n;++p){
if(phi[p]==p){
for(int multiple=p;multiple<=n;multiple+=p){
phi[multiple]-=phi[multiple]/p;
}
}
}
long long answer=1;
for(int d=2;d<=n;++d){
answer+=phi[d];
}
cout<<answer<<'\n';
}