So, i recently found this interesting problem:
https://szkopul.edu.pl/problemset/problem/nYCgpBEkq_hw9S-QaoEOOKCI/site/?key=statement
I've been stuck on it for the past couple of days, and I was hoping someone could help me out — maybe share some ideas or give me a small hint?
Any input would be really appreciated!
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
I don't know the authors' solution, but here is mine:
What is the maximum length of interval, that could be the answer?
Approximately about 53
Intuition suggests that the length should be very small. Let’s try to prove that.
Consider the interval [L, R]. Notice that $$$LCM \ge \prod_{i=1}^{n} p_i$$$, where $$$p_i$$$ — prime number, n — the number of distinct prime factors in the product of all numbers from L to R. In the problem we are searching for an $$$LCM \le 10^{18}$$$. Note that the product of the first primes up to 53 (inclusive) already exceeds $$$10^{18}$$$. The last thing to note is that since on a segment of length K there is at least one number that is divisible by K, then on a segment of length 53 for each prime number from 2 to 53 there is at least one that is divisible by it
Consider two types of intervals: those with length 2 and those with length greater than 2
The solution described here is for $$$LCM \le 10^9$$$, but this solution is useful to get the full solution
$$$gcd(x; x+q) \le q$$$, where q — natural number
Let's try to find the upper limit on the left boundary of the interval
To do this, consider an interval of length 3, since as the interval length increases, the LCM does not decrease. Let's it will be interval [L; L+2]. Notice that $$$gcd(L; L+1) = 1$$$ and $$$gcd(L+1; L+2) = 1$$$ and $$$gcd(L; L+2) \le 2$$$, so to find the upper boundary for L, solve this equation: $$$L(L+1)(L+2)/2 \le 10^{18}$$$. It gives us that $$$L \lt 1.3e+6$$$. So, using the small length of the segments, we simply iterate over L and the length and save the answers for each interval. Despite the fact that we have already reached the required asymptotics in time, this problem has a memory limit of 128 MB, which is why this solution only passes the first two groups of tests, if we recalculate L for $$$LCM \le 10^9$$$
Consider interval [L; L+1] and required LCM (M)
$$$gcd(L; L+1)=1$$$, then $$$LCM(L; L+1) = L*(L+1) = M$$$. We can find L with $$$O(1)$$$ as quadratic equation or using binary search
Before reading, you need to read Hint 3, because this hint is an improvement on the previous solution
Instead of two groups, consider three: interval length is 2; interval length is 3; interval length is greater than 3
Before reading the solution, read all the Hints
Consider three groups: interval length is 2; interval length is 3; interval length is greater than 3
What to do with intervals of length 2 was discussed in (Hint 3)
As now we use brute force for interval length greater than 3, we should solve this equation (for more details look (Hint 3)): $$$L*(L+1)*(L+2)*(L+3)/12 \le 10^{18}$$$. It gives us $$$L \lt 6e+4$$$ and now we are within the memory limit
For intervals of length 3, notice that $$$LCM(L; L+1; L+2) = L*(L+1)*(L+2)$$$ if L is odd, and $$$LCM(L; L+1; L+2) = L*(L+1)*(L+2)/2$$$ if L is even. We would like to find L such that $$$LCM(L; L+1; L+2) = M$$$ (required LCM). Just run binary search for even and odd L separately and choose the best intervals
Among all the intervals found, we select the one with the smallest L (in case of equality with the smallest R)
ty! You helped a lot with those hints. Solution looks much easier than i thought