{"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 days, a new math concept was created.\n\nAs 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.\n\nSo, 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)\n\nNotice that $\\text{exlog}_f(1)$ is always equal to $0$.\n\nThis 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$).\n\n\"Class is over! Don't forget to do your homework!\" Here it is: \\\\sum_{i=1}^n \\\\text{exlog}_f(i)\n\nHelp children to do their homework. Since the value can be very big, you need to find the answer modulo $2^{32}$.\n\n## Input\n\nThe 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$).\n\n## Output\n\nPrint the answer modulo $2^{32}$.\n\n[samples]\n\n## Note\n\nIn the first sample:\n\n$\\text{exlog}_f(1) = 0$\n\n$\\text{exlog}_f(2) = 2$\n\n$\\text{exlog}_f(3) = 3$\n\n$\\text{exlog}_f(4) = 2 + 2 = 4$\n\n$\\text{exlog}_f(5) = 5$\n\n$\\text{exlog}_f(6) = 2 + 3 = 5$\n\n$\\text{exlog}_f(7) = 7$\n\n$\\text{exlog}_f(8) = 2 + 2 + 2 = 6$\n\n$\\text{exlog}_f(9) = 3 + 3 = 6$\n\n$\\text{exlog}_f(10) = 2 + 5 = 7$\n\n$\\text{exlog}_f(11) = 11$\n\n$\\text{exlog}_f(12) = 2 + 2 + 3 = 7$\n\n$\\sum_{i=1}^{12} \\text{exlog}_f(i)=63$\n\nIn the second sample:\n\n$\\text{exlog}_f(1) = 0$\n\n$\\text{exlog}_f(2) = (1 \\times 2^3 + 2 \\times 2^2 + 3 \\times 2 + 4) = 26$\n\n$\\text{exlog}_f(3) = (1 \\times 3^3 + 2 \\times 3^2 + 3 \\times 3 + 4) = 58$\n\n$\\text{exlog}_f(4) = 2 \\times \\text{exlog}_f(2) = 52$\n\n$\\sum_{i=1}^4 \\text{exlog}_f(i)=0+26+58+52=136$","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_1^{a_1} p_2^{a_2}... p_k^{a_k}$ 是一个整数的质因数分解。问题是这个函数在其定义中使用了自身，因此难以计算。\n\n于是，中立区的数学家们发明了如下定义：$$ \\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) $$\n\n注意，$\\text{exlog}_f (1)$ 始终等于 $0$。\n\n对于任意函数 $f$，这个概念对孩子们来说都太难了。因此老师告诉他们，在日常使用中 $f$ 只能是一个次数不超过 $3$ 的多项式（即 $f (x) = A x^3 + B x^2 + C x + D$）。\n\n\"课上完了！别忘了做作业！\" 作业如下：$$ \\sum_{i=1}^n \\text{exlog}_f(i) $$\n\n请帮助孩子们完成作业。由于答案可能非常大，你需要计算答案对 $2^{32}$ 取模的结果。\n\n输入仅一行，包含五个整数 $n$, $A$, $B$, $C$, $D$（$1 \\leq n \\leq 3 \\cdot 10^8$，$0 \\leq A, B, C, D \\leq 10^6$）。\n\n请输出答案对 $2^{32}$ 取模的结果。\n\n在第一个样例中：\n\n$\\text{exlog}_f (1) = 0$\n\n$\\text{exlog}_f (2) = 2$\n\n$\\text{exlog}_f (3) = 3$\n\n$\\text{exlog}_f (4) = 2 + 2 = 4$\n\n$\\text{exlog}_f (5) = 5$\n\n$\\text{exlog}_f (6) = 2 + 3 = 5$\n\n$\\text{exlog}_f (7) = 7$\n\n$\\text{exlog}_f (8) = 2 + 2 + 2 = 6$\n\n$\\text{exlog}_f (9) = 3 + 3 = 6$\n\n$\\text{exlog}_f (10) = 2 + 5 = 7$\n\n$\\text{exlog}_f (11) = 11$\n\n$\\text{exlog}_f (12) = 2 + 2 + 3 = 7$\n\n$\\sum_{i = 1}^{12} \\text{exlog}_f (i) = 63$\n\n在第二个样例中：\n\n$\\text{exlog}_f (1) = 0$\n\n$\\text{exlog}_f (2) = (1 \\times 2^3 + 2 \\times 2^2 + 3 \\times 2 + 4) = 26$\n\n$\\text{exlog}_f (3) = (1 \\times 3^3 + 2 \\times 3^2 + 3 \\times 3 + 4) = 58$\n\n$\\text{exlog}_f (4) = 2 \\times \\text{exlog}_f (2) = 52$\n\n$\\sum_{i = 1}^4 \\text{exlog}_f (i) = 0 + 26 + 58 + 52 = 136$\n\n## Input\n\n输入仅一行，包含五个整数 $n$, $A$, $B$, $C$, $D$（$1 \\leq n \\leq 3 \\cdot 10^8$，$0 \\leq A, B, C, D \\leq 10^6$）。\n\n## Output\n\n请输出答案对 $2^{32}$ 取模的结果。\n\n[samples]\n\n## Note\n\n在第一个样例中：$\\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$。","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 factorization.  \nDefine the function:  \n$$\n\\text{exlog}_f(i) = \\sum_{p \\text{ prime}} e_p(i) \\cdot f(p)\n$$  \nwith $ \\text{exlog}_f(1) = 0 $.\n\n**Constraints**  \nGiven integers $ n, A, B, C, D $ such that:  \n- $ 1 \\leq n \\leq 3 \\cdot 10^8 $  \n- $ 0 \\leq A, B, C, D \\leq 10^6 $\n\n**Objective**  \nCompute:  \n$$\n\\sum_{i=1}^n \\text{exlog}_f(i) \\mod 2^{32}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1017F","tags":["brute force","math"],"sample_group":[["12 0 0 1 0","63"],["4 1 2 3 4","136"]],"created_at":"2026-03-03 11:00:39"}}