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

yoihito's blog

By yoihito, 8 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

»
8 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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      8 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 :)

      • »
        »
        »
        »
        8 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 :)
    • »
      »
      »
      8 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];
      
      • »
        »
        »
        »
        8 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)))

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow. That is a clever use of the Divisor Sum property of the Euler Totient Function.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I know this is an old comment haha, but shouldn't phi[1] = 1 ? Since gcd(0, 1) = 1?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes. You should initialize $$$\phi(1)=1$$$ and start the bottom loop from $$$i = 2$$$.

»
8 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 .