Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### yoihito's blog

By yoihito, 8 years ago, , Problem Enumerating Rational Numbers
I don't know how to solve this problem, with the help of Euler's function. Can you explain me the idea for this problem? Comments (10)
 » Ok, got accepted. First notice: Max denominator is 2*10^5 (from test case). Second notice: Each denominator have exatcly phi(denominator) fractions. After this notices you can precalculate euler functions for first 2*10^5 numbers. For determine denominator you can precalc prefix sum of euler functions and easily find denominator with binary search in this array. After this we need to determine numerator. If determinator is num, it's exatcly (k - sum[num - 1]) coprime number with prime. It's step you can simply do with iterate from 1 to num and calc gcd.
•  » » I got TLE. http://pastebin.com/2rFPsEHx
•  » » » 8 years ago, # ^ | ← Rev. 2 →   Ah, you cant calc euler function for 1...n on each test case, too expensive(n * sqrt(n)), precalc it :)
•  » » » » Thank you, I just try to write binary search and understand that I should precalc euler function :)
•  » » » Also, it's a useful fact that you can calculate euler function for numbers 1... n in time, using this approach: phi = phi = 0; for (int i=2; i
•  » » » » Wow, thnks for that. But it seems like the complexity is O(n*log(log(n)))
•  » » » » Wow. That is a clever use of the Divisor Sum property of the Euler Totient Function.
•  » » » » I know this is an old comment haha, but shouldn't phi = 1` ? Since gcd(0, 1) = 1?
•  » » » » » Yes. You should initialize $\phi(1)=1$ and start the bottom loop from $i = 2$.
 » We had asked a very similar question with higher constraints during IOPC last year. The problem can be found here .