Enumerating Rational Numbers(UVa online Judge #11327)

→ Обратите внимание

До соревнования
Codeforces Round (Div. 2)
6 дней

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3657
3	jiangly	3638
4	turmax	3442
5	tourist	3380
6	Um_nik	3353
7	strapple	3350
8	squareOf105	3346
9	heuristica	3322
10	maroonrk	3310

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
4	Um_nik	143
6	Errichto	139
7	adamant	137
8	BledDest	134
9	maroonrk	133
10	qwexd	130

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Enumerating Rational Numbers(UVa online Judge #11327)

Автор yoihito, 15 лет назад, По-английски

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?

yoihito
15 лет назад
11

Комментарии (8)

Показать архивные | Написать комментарий?

yarrr

15 лет назад, скрыть # |

← Rev. 2 →

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

→ Ответить

yarrr

15 лет назад, скрыть # |

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.

Code: http://pastie.org/3238844

→ Ответить

yoihito

15 лет назад, скрыть # ^ |

I got TLE.
http://pastebin.com/2rFPsEHx

→ Ответить

yarrr

15 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

yoihito

15 лет назад, скрыть # ^ |

Thank you, I just try to write binary search and understand that I should precalc euler function :)

→ Ответить

_jte_

15 лет назад, скрыть # ^ |

+13

Also, it's a useful fact that you can calculate euler function for numbers 1... n in $\text{[math]}$ 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];

→ Ответить

Laise

15 лет назад, скрыть # ^ |

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

→ Ответить

razimantv

15 лет назад, скрыть # |

We had asked a very similar question with higher constraints during IOPC last year. The problem can be found here.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 18.10.2026 09:29:19 (i1).

Десктопная версия, переключиться на мобильную.

При поддержке