Consider a sequence a = a1, a2, ..., an of length n. The sequence a is called beautiful if it satisfies both of the following conditions:
For all i from 1 to n, the value of a[i] is between 1 and m, inclusive.
For all i from 1 to n — 1, a[i] is a divisor of a[i + 1].
Count how many such beautiful sequences exist.
Since the answer can be very large, output the result modulo 998244353.
Constraints:
1 ≤ n, m ≤ 3 × 10⁸
Time limit: 5s
Sample input:
3 6
Sample output:
25
Could you all please help me? I really appreciate it!
If the last value is $$$a = \prod_{i} p_i^{e_i}$$$ for some primes $$$p_i$$$, Then for each prime factor separately, the number of occurrences among the $$$n$$$ positions can only increase. Therefore, for $$$p_i$$$, there are $$$\binom{n-1+e_i}{e_i}$$$ possible ways of distributing. Since $$$e_i$$$ is at most $$$\log_2(m)$$$, we just precompute all possible values. Now the total number of sequences for last element $$$a$$$ is the product of $$$\binom{n-1+e_i}{e_i}$$$ for all primes. We can now do this for all possible last numbers with sieve of eratosthenes in $$$O(m \log\log(m))$$$, which is sufficient given the bounds.
Sorry, but since m ≤ 3e8, creating an array for storage is completely impossible.
I've also implemented this algorithm considering it as a specific solution for n, m ≤ 2e6.
Look up segmented sieve. You can do it with sqrt(m) memory :) If you want faster time, you can use min25 sieve, and then it is $$$\tilde{O}(m^{\frac{2}{3}})$$$ time aswell, but given the constraints this is not even needed. If you want an even faster solution, you can precompute classes.
Thank you, I guess I have to learn the Min25 sieve now, because when I manually ran the segmented sieve with n, m = 3e7, it already took about 1–2 seconds, so it can’t be optimized further.
min25 is really overkill. If it is still too slow, notice that you only care about the count of $$$e_i$$$'s. That is, how many $$$e_i$$$'s are 1, how many are 2, etc. This gives us some classes. For example, $$$12=2^2\times 3$$$ is in the class $$$1,1,0,0,0,...$$$, since it has one prime once and one prime twice. There are only very few possible such classes. Instead of directly computing the answer, use your segmented sieve to count how many times each class appears in each segment, and store the results in a table (i mean compute locally on your own computer, where there is no 5s timelimit). This way, you only need to compute the last segment from scratch.
Also, segmented sieve should really not be that slow.
You mean using a segmented sieve combined with the trick of storing precomputed values in constant arrays, like the number of elements with exponent , etc., and then computing the answer?
yes. Then the actual runtime is O(B), and the code size is ~300 m / B, where B is the blocksize. B = 3e6 should do the trick.
Oh oh, thank you — even though it’ll probably get me “judged” :))))
I would really check your previous implementation. I implemented it without any tricks, and max test runs in < 2 seconds. It should not be as slow as your code is
Maybe I went a bit overkill and couldn’t come up with anything simpler, so I ended up implementing something quite similar to the Min25 sieve combined with Lagrange interpolation. Anyway, thank you very much! P.S.: I'm still a bit unsure whether one particular problem truly requires using the Min25 sieve or not.