The problem can be found here: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4878
I know the final answer but idk how to get it myself.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:40:29
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:40:29
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 09:54:31 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Apologies. I misread the problem.
Consider two fractions $$$\frac{x}{y}$$$ and $$$\frac{a}{b}$$$. And let's assume that $$$b \geqslant y$$$. For a fixed $$$a$$$ we are interested in such fractions $$$\frac{x}{y}$$$ that $$$|ay - bx| = 1$$$. Also we must pick only fractions with $$$gcd(x,y) = 1$$$, but that's not a problem, since other fractions will not be a solution for this equation.
Let's first consider case $$$ay - bx = +1$$$. Since $$$gcd(a, b) = 1$$$, there always exist infinite many solutions in the form $$$x = at + x_0$$$, $$$y = bt + y_0$$$. Remember, we decided to choose $$$y \leqslant b$$$. Also, $$$y = b$$$ or $$$y = 0$$$ are not solutions (if $$$b \neq 1$$$, but that's a special case). So let's choose $$$t$$$ such that $$$1 \leqslant y \leqslant b - 1$$$. And it can be seen that for that $$$y$$$, $$$x$$$ will be a legit numerator (that is, $$$0\leqslant x < y$$$).
So for every $$$a$$$ such that $$$gcd(a, b) = 1$$$, we have exactly one solution. One more comes from $$$ay - bx = -1$$$. That gives us $$$2\sum\limits_{i=1}^n \varphi(i)$$$. And from that we have to subtract number of consecutive pairs, which is $$$1$$$ smaller than number of fractions, which is $$$\sum\limits_{i=1}^n \varphi(n)+1$$$.
That gives $$$\sum\limits_{i=1}^n \varphi(i)$$$, but I believe that $$$\pm 1$$$ comes from the case $$$b = 1$$$
Hey,
thank you for the detailed answer. However, there are two parts that are not very clear to me.
$$$1 \leq y \leq b - 1$$$
$$$1 \leq bt + y_0 \leq b - 1$$$
$$$ \frac{1 - y_0}{b} \leq t \leq \frac{b - 1 - y_0}{b} $$$
So the size of the range of possible values of $$$t$$$ is:
$$$\frac{b - 1 - y_0 - (1 - y_0)}{b} = \frac{b - 2}{b}$$$
Which is actually less than $$$1$$$ so something is clearly lacking my understanding.
For the first part: we can search for $$$t$$$ such that $$$0 \leqslant bt + y_0 \leqslant b - 1$$$. Then there are exactly $$$b$$$ integers in $$$[0; b-1]$$$, so there will be exactly one solution. But $$$y = 0$$$ is not a solution (because $$$-bx \neq 1$$$ for $$$b \neq 1$$$)
About $$$x$$$: from $$$ay - bx = 1$$$, $$$x = \frac{ay - 1}{b}$$$. For $$$y \in [1;b-1]$$$, $$$0 < ay - 1 < by$$$ (since $$$a < b$$$), so $$$0 < x < y$$$
Thanks a lot, Maksim. It is perfectly clear to me right now. I just wanna verify one last thing.
it should be $$$0 \leq x \leq y$$$. Right?
$$$0 \leq y$$$ since we cannot guarantee that $$$ay - 1 > 0$$$, but that won't be a problem for us since $$$\frac{0}{1}$$$ is the only pair with $$$x == 0$$$ (because $$$gcd(x, y) == 1$$$) and it is part of our farey sequence and should be counted.
$$$x \leq y$$$ comes from the second equation $$$ay - bx = -1$$$. as $$$x = \frac{ay + 1}{b}$$$ this time. But this also won't be a problem for us since the only pair that will have $$$x == y$$$ is $$$\frac{1}{1}$$$ (also because $$$gcd(x, y) == 1$$$ and it is also part of the farey sequence and should be counted.
Also for those who are interested on where I went wrong in my proof of the first part: We are not interested in the 'size' of the range of possible values of $$$t$$$. We are interested in the number of possible integer solutions for $$$t$$$. The size could be less than $$$1$$$ and still span an integer. e.g. [0.9, 1.1] has size 0.2 but still spans an integer in the middle.
To be fair, I didn't care much about less or less-equal, or $$$\pm 1$$$, because you already had an answer and just asked for an explanation :)
Yes, $$$0 \leqslant x$$$, not $$$0 < x$$$, that's my mistake.
And $$$x \leqslant y$$$ is a correct sign too, I agree, sorry for this.
I was thinking about considering $$$b=1$$$ as a special case, but $$$y=1$$$ is not a special case, so I should have thought about that.
No worries :). I'm just always super afraid to be doing something wrong when dealing with math and always wanna verify I'm not missing an obvious thing. Thanks again!
For two fractions $$$\frac{m_1}{n_1}$$$ and $$$\frac{m_2}{n_2}$$$ to have $$$m_2 n_1 - m_1 n_2 = 1$$$ They must be adjacent in some farey sequence $$$F_x$$$, but not necessarily $$$F_n$$$. So we can reframe the problem as "Count the number of pairs of fractions that are in $$$F_n$$$ and were previously neighbors in $$$F_i$$$, $$$i < n$$$
The sequence $$$F_n$$$ has $$$\phi(n)$$$ extra elements from $$$F_{n-1}$$$ (as all numbers which are not coprime will need to be simplified, thus denominator will decrease, thus won't be new fractions). Every extra element "separates" two fractions that were previously adjacent, i.e. it adds $$$\phi(n)$$$ pairs. Formally, $$$A_1 = 0$$$, $$$A_n = A_{n-1} + \phi(n)$$$.
From there it's easy to see that for $$$n \geq 2$$$: $$$A_n = \sum_{i=2}^{n}{\phi(i)}=\sum_{i=1}^{n}{\phi(i)} - \phi(1) = \sum_{i=1}^{n}{\phi(i)} - 1$$$.
Thank you!