F. The Neutral Zone

Codeforces

IDCF1017F

Time5000ms

Memory16MB

Difficulty—

brute forcemath

English · Original

Chinese · Translation

Formal · Original

**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 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 Print the answer modulo $2^{32}$. [samples] ## 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$

*注意：内存限制特殊！* 战争结束后，中立区被毁的城市得到了重建，孩子们也重返校园。战争改变了世界，也改变了教育。在那些艰难的日子里，诞生了一个新的数学概念。正如我们所知，对数函数可以描述为：$$ \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 $$ 其中 $p_1^{a_1} p_2^{a_2}... p_k^{a_k}$ 是一个整数的质因数分解。问题是这个函数在其定义中使用了自身，因此难以计算。于是，中立区的数学家们发明了如下定义：$$ \text{exlog}_f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k) $$ 注意，$\text{exlog}_f (1)$ 始终等于 $0$。对于任意函数 $f$，这个概念对孩子们来说都太难了。因此老师告诉他们，在日常使用中 $f$ 只能是一个次数不超过 $3$ 的多项式（即 $f (x) = A x^3 + B x^2 + C x + D$）。 "课上完了！别忘了做作业！" 作业如下：$$ \sum_{i=1}^n \text{exlog}_f(i) $$ 请帮助孩子们完成作业。由于答案可能非常大，你需要计算答案对 $2^{32}$ 取模的结果。输入仅一行，包含五个整数 $n$, $A$, $B$, $C$, $D$（$1 \leq n \leq 3 \cdot 10^8$，$0 \leq A, B, C, D \leq 10^6$）。请输出答案对 $2^{32}$ 取模的结果。在第一个样例中： $\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$ 在第二个样例中： $\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$ ## Input 输入仅一行，包含五个整数 $n$, $A$, $B$, $C$, $D$（$1 \leq n \leq 3 \cdot 10^8$，$0 \leq A, B, C, D \leq 10^6$）。 ## Output 请输出答案对 $2^{32}$ 取模的结果。 [samples] ## Note 在第一个样例中：$\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$。在第二个样例中：$\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$。

**Definitions** Let $ f(x) = A x^3 + B x^2 + C x + D $, where $ A, B, C, D \in \mathbb{Z}_{\geq 0} $. For any integer $ i \geq 1 $, let $ i = \prod_{p \text{ prime}} p^{e_p(i)} $ be its prime factorization. Define the function: $$ \text{exlog}_f(i) = \sum_{p \text{ prime}} e_p(i) \cdot f(p) $$ with $ \text{exlog}_f(1) = 0 $. **Constraints** Given integers $ n, A, B, C, D $ such that: - $ 1 \leq n \leq 3 \cdot 10^8 $ - $ 0 \leq A, B, C, D \leq 10^6 $ **Objective** Compute: $$ \sum_{i=1}^n \text{exlog}_f(i) \mod 2^{32} $$

Samples

Input #1

12 0 0 1 0

Output #1

Input #2

4 1 2 3 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. The Neutral Zone",
    "description": {
      "content": "**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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 16384
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1017F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**Notice: unusual memory limit!**\n\nAfter the war, destroyed cities in the neutral zone were restored. And children went back to school.\n\nThe war changed the world, as well as education. In those hard ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "*注意：内存限制特殊！*\n\n战争结束后，中立区被毁的城市得到了重建，孩子们也重返校园。\n\n战争改变了世界，也改变了教育。在那些艰难的日子里，诞生了一个新的数学概念。\n\n正如我们所知，对数函数可以描述为：$$ \\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 $$ 其中 $p...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f(x) = A x^3 + B x^2 + C x + D $, where $ A, B, C, D \\in \\mathbb{Z}_{\\geq 0} $.  \nFor any integer $ i \\geq 1 $, let $ i = \\prod_{p \\text{ prime}} p^{e_p(i)} $ be its prime fact...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments