2 ms·
The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fa
by kevinventullo 7y ago
The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fairly early on assuming e.g. N << 2^M.
- chupasaurus 7y ago> you can stop as soon as the lcm's of your subsets exceed N Actually if N < 2 * lcm, because you can't use the fact that the distribution of multiples is the same on (1, lcm) and (k * lcm+1, lcm(k+1)) while you still have to count on (N - N mod lcm + 1, N).