Блог пользователя yoihito

Enumerating Rational Numbers(UVa online Judge #11327)
Автор yoihito, 13 лет назад, По-английски

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
  • Проголосовать: не нравится

»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не тот язык, извиняюсь.

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I got TLE.
    http://pastebin.com/2rFPsEHx
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Thank you, I just try to write binary search and understand that I should precalc euler function :)
        → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +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<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];
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
We had asked a very similar question with higher constraints during IOPC last year. The problem can be found here.
→ Ответить