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


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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.