yoihito's blog

Enumerating Rational Numbers(UVa online Judge #11327)
By yoihito, 13 years ago, In English

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?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I got TLE.
    http://pastebin.com/2rFPsEHx
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ah, you cant calc euler function for 1...n on each test case, too expensive(n * sqrt(n)), precalc it :)

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thank you, I just try to write binary search and understand that I should precalc euler function :)
        → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it
      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<maxn; ++i)
    phi[i] = i - 1;
for (int i=1; i<maxn; ++i)
        for (int j=i+i; j<maxn; j+=i)
                 phi[j] -= phi[i];
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, thnks for that. But it seems like the complexity is O(n*log(log(n)))

        → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
We had asked a very similar question with higher constraints during IOPC last year. The problem can be found here.
→ Reply