### 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?

• +4

 » 8 years ago, # |   +8 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.
•  » » 8 years ago, # ^ |   0 I got TLE.http://pastebin.com/2rFPsEHx
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Ah, you cant calc euler function for 1...n on each test case, too expensive(n * sqrt(n)), precalc it :)
•  » » » » 8 years ago, # ^ |   0 Thank you, I just try to write binary search and understand that I should precalc euler function :)
•  » » » 8 years ago, # ^ |   +13 Also, it's a useful fact that you can calculate euler function for numbers 1... n in time, using this approach: phi[0] = phi[1] = 0; for (int i=2; i
•  » » » » 8 years ago, # ^ |   0 Wow, thnks for that. But it seems like the complexity is O(n*log(log(n)))
•  » » » » 7 weeks ago, # ^ |   0 Wow. That is a clever use of the Divisor Sum property of the Euler Totient Function.
•  » » » » 7 weeks ago, # ^ |   0 I know this is an old comment haha, but shouldn't phi[1] = 1` ? Since gcd(0, 1) = 1?
•  » » » » » 6 weeks ago, # ^ |   0 Yes. You should initialize $\phi(1)=1$ and start the bottom loop from $i = 2$.
 » 8 years ago, # |   0 We had asked a very similar question with higher constraints during IOPC last year. The problem can be found here.