The Neutral Zone
Contest: Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)
Difficulty rating: 2500
Tags: brute force, math

Notice: unusual memory limit!

After the war, destroyed cities in the neutral zone were restored. And children went back to school.

The war changed the world, as well as education. In those hard days, a new math concept was created.

As we all know, logarithm function can be described as: $$$$$$ \log(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 \log p_1 + a_2 \log p_2 + ... + a_k \log p_k $$$$$$ Where $$$p_1^{a_1}p_2^{a_2}...p_k^{a_2}$$$ is the prime factorization of a integer. A problem is that the function uses itself in the definition. That is why it is hard to calculate.

So, the mathematicians from the neutral zone invented this: $$$$$$ \text{exlog}_f(p_1^{a_1}p_2^{a_2}...p_k^{a_2}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) $$$$$$

Notice that $$$\text{exlog}_f(1)$$$ is always equal to $$$0$$$.

This concept for any function $$$f$$$ was too hard for children. So teachers told them that $$$f$$$ can only be a polynomial of degree no more than $$$3$$$ in daily uses (i.e., $$$f(x) = Ax^3+Bx^2+Cx+D$$$).

"Class is over! Don't forget to do your homework!" Here it is: $$$$$$ \sum_{i=1}^n \text{exlog}_f(i) $$$$$$

Help children to do their homework. Since the value can be very big, you need to find the answer modulo $$$2^{32}$$$.

Input format:
The only line contains five integers $$$n$$$, $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$ ($$$1 \le n \le 3 \cdot 10^8$$$, $$$0 \le A,B,C,D \le 10^6$$$).

Output format:
Print the answer modulo $$$2^{32}$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 16.0 MB

Note:
In the first sample:

$$$\text{exlog}_f(1) = 0$$$

$$$\text{exlog}_f(2) = 2$$$

$$$\text{exlog}_f(3) = 3$$$

$$$\text{exlog}_f(4) = 2 + 2 = 4$$$

$$$\text{exlog}_f(5) = 5$$$

$$$\text{exlog}_f(6) = 2 + 3 = 5$$$

$$$\text{exlog}_f(7) = 7$$$

$$$\text{exlog}_f(8) = 2 + 2 + 2 = 6$$$

$$$\text{exlog}_f(9) = 3 + 3 = 6$$$

$$$\text{exlog}_f(10) = 2 + 5 = 7$$$

$$$\text{exlog}_f(11) = 11$$$

$$$\text{exlog}_f(12) = 2 + 2 + 3 = 7$$$

$$$ \sum_{i=1}^{12} \text{exlog}_f(i)=63 $$$

In the second sample:

$$$\text{exlog}_f(1) = 0$$$

$$$\text{exlog}_f(2) = (1 \times 2^3 + 2 \times 2^2 + 3 \times 2 + 4) = 26$$$

$$$\text{exlog}_f(3) = (1 \times 3^3 + 2 \times 3^2 + 3 \times 3 + 4) = 58$$$

$$$\text{exlog}_f(4) = 2 \times \text{exlog}_f(2) = 52$$$

$$$ \sum_{i=1}^4 \text{exlog}_f(i)=0+26+58+52=136 $$$

Example input:
12 0 0 1 0

Example output:
63

Example input:
4 1 2 3 4

Example output:
136

Editorial:
First forget about the memory limit part.
Instead of enumerating all integers and count its $$$\text{exlog}_f$$$ value, we enumerate all primes and count its contribution.
It is obvious that prime $$$p$$$'s contribution is: $$$$$$ f(p)\bigg(\bigg\lfloor\frac{n}{p}\bigg\rfloor+\bigg\lfloor\frac{n}{p^2}\bigg\rfloor+\bigg\lfloor\frac{n}{p^3}\bigg\rfloor+...\bigg) $$$$$$ (The second part is the number of times it occurs in total in integers less than or equal to $$$n$$$, you can examine and feel that manually).
Brute-force this thing is actually $$$O(n)$$$: since there are only $$$O(\frac{n}{\ln n})$$$ primes less than or equal to $$$n$$$ and calculate the second part for each of them cost $$$O(\log_p n)$$$ times.
Now the problem is on sieving the primes. Use Eratosthenes's sieve instead of Euler's, then the only memory cost is the cross-out table.
Use a 'bitset' to store the cross-out table and you'll get a memory cost for about $$$37.5 MB$$$.
Key observation: except $$$2$$$ and $$$3$$$, all primes $$$p$$$ satisfy $$$p \equiv \pm 1 \pmod 6$$$.
Then just store these positions with $$$\frac{37.5MB}{3} = 12.5 MB$$$.
You can also use this observation to optimize your code's running time.
Complexity: $$$O(n \log \log n)$$$. That's the running time of Eratosthenes's sieve.