SPOJ.com - Problem LUDIC2

LUDIC2 - Ludic Numbers (hard)

#sub-linear

Find the number of Ludic numbers less than or equal to $N$.

The first line contains an integer $N$ ($1 \le N \le 10^{11}$).

Output the number of Ludic numbers less than or equal to $N$.

Input:
100000000000

Output:
3603128157



	Oleg: 2024-01-30 05:44:31 Amazing problem!
	kamol_paul: 2021-04-21 21:41:19 Is there any editorial of this problem?
	dacin21: 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
	Min_25: 2018-05-11 12:20:46 @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
	dacin21: 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.