| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 170 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 5 | -is-this-fft- | 158 |
| 7 | adamant | 154 |
| 7 | Dominater069 | 154 |
| 9 | awoo | 153 |
| 10 | luogu_official | 152 |
Can someone please help me understand or prove this (intuitively or formally)?
We are given an integer x < 1e18, How can we determine a lower bound on the length of a range [a, b], such that there is at least one number in [a, b] that is coprime to x?
I would say use the idea of euler's formula, x <= 1e18 would have atmax 20 primes.
Let the length of range be L, after using each of the primes to discard numbers, number of coprime numbers in range would probably be
$$$N = L * (1 - 1 / 2) * (1 - 1 / 3) * (1 - 1 / 5) ...$$$
for first 20 primes thats about $$$0.12L$$$. So for about $$$L >= 10$$$ you should expect to see atleast one coprime number.
I know this may be a totally wrong way of proving, but thats just my intution for this.
This is wrong.
You are implicitly using the lemma:
However, once you do this for one of the primes, the range is no longer consecutive, and this lemma does not apply. It might be the case that the remaining numbers are all divisible by the next prime considered.
The state-of-the-art approximation for $$$g(n)$$$ is
$$$g(n) = O(\log^{2} n)$$$ reference
where $$$g(n)$$$ is the Ordinary Jacobsthal function (which for instance is defined here) defined as the smallest positive integer such that every sequence of $$$g(n)$$$ consecutive positive integers contains an integer relatively prime to $$$n$$$.
As to the OP's question, assuming that he is keen to prove the solution for Problem about GCD, I believe the lemma that will actually prove the solution is:
Maybe it is possible to prove that $$$k=log(A)$$$? No idea though.
rather than proving an unsolved conjecture 🤪
Your text to link here... This is what i followed, but one could think of it as its obvious we wont be expected to check all pairs given range of l and r is too too big. Prime gap was the primary idea after contest.