| Submit | All submissions | Best solutions | Back to list |
LUDIC2 - Ludic Numbers (hard) |
Find the number of Ludic numbers less than or equal to $N$.
Input
The first line contains an integer $N$ ($1 \le N \le 10^{11}$).
Output
Output the number of Ludic numbers less than or equal to $N$.
Example
Input
100000000000
Output
3603128157
Note
- See LUDIC1 for an easier version.
- Other references for the Ludic numbers: Ludic numbers or A003309.
| Added by: | Min_25 |
| Date: | 2018-04-12 |
| Time limit: | 25s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
2024-01-30 05:44:31 Oleg
Amazing problem! |
|
|
2021-04-21 21:41:19
Is there any editorial of this problem? |
|
|
2018-05-11 13:11:51
@Min_25 Thanks for you comment. I just optimized my LUDIC2 solution to answer queries below 8e7 in O(1) and reduced the recursion threshold to N^{1/2}/3. It's quite a bit faster now. My timing for N = 10^{12} is around 19s too (after fixing some overflows). I also submitted this solution to LUDIC1 and it was a lot faster. The sieve was somewhat optimized as I hopped to run it up to 1e9 at compile-time and then answer queries in O(1). But then it was to slow and didn't work with constexpr. Last edit: 2018-05-11 13:12:30 |
|
|
2018-05-11 12:20:46 Min_25
@dacin21: Thank you for solving the problem ! My (worst-case) running times are about 3.8 seconds for LUDIC1 or LUDIC2, and about 20 seconds for N = 10^{12}. As for the sieve, your algorithm seems about 2~3 times faster than mine! So, it is not slow but the fastest one so far. (The "query" part in LUDIC1 can be optimized.) As for LUDIC2, I think the running time can be largely reduced by doing "piecewise-linear stuff". Last edit: 2018-05-11 12:34:15 |
|
|
2018-05-11 10:42:23
@Min_25 Thanks for posting this problem. I liked the idea I used to optimize from LUDIC1 to LUDIC2. How fast does your solution run? My solution builds on top of my slow LUDIC1 solution, so it's quite slow. |
RSS