{"problem":{"name":"除法题","description":{"content":"给定大小为 $n$ 的集合 $a$，保证其中元素互不相同且均为正整数。 如果我们从中**按顺序**取出三个元素 $a, b, c$，则共有 $n \\cdot (n-1) \\cdot (n-2)$ 种不同的选择方案。 现在对于一种选择方案 $(a,b,c)$，定义其权值为 $\\Bigl\\lfloor\\dfrac{a}{b}\\Bigr\\rfloor\\Bigl\\lfloor\\dfrac{a}{c}\\","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9148"},"statements":[{"statement_type":"Markdown","content":"给定大小为 $n$ 的集合 $a$，保证其中元素互不相同且均为正整数。\n\n如果我们从中**按顺序**取出三个元素 $a, b, c$，则共有 $n \\cdot (n-1) \\cdot (n-2)$ 种不同的选择方案。\n\n现在对于一种选择方案 $(a,b,c)$，定义其权值为 $\\Bigl\\lfloor\\dfrac{a}{b}\\Bigr\\rfloor\\Bigl\\lfloor\\dfrac{a}{c}\\Bigr\\rfloor\\Bigl\\lfloor\\dfrac{b}{c}\\Bigr\\rfloor$。\n\n你需要对所有的选择方案计算权值的总和，你只需输出这个总和对 $2^{32}$ 取模的结果。\n\n注：$\\lfloor a\\rfloor$ 表示不大于 $a$ 的最大整数。如 $\\lfloor 2.4\\rfloor=2$、$\\lfloor 5\\rfloor=5$。\n\n## Input\n\n第一行，一个正整数 $n$，表示序列的长度。\n\n第二行，$n$ 个正整数 $a_1, a_2, \\ldots, a_n$，每个数描述了集合 $a$ 的一个元素，这些数互不相同。\n\n## Output\n\n输出一行一个整数，表示答案对 $2^{32}$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 \\#1】**\n\n对于样例 \\#1，权值不为 $0$ 的选择方案只有以下几种：\n\n- $(3,2,1)$，权值为 $6$。\n- $(4,2,1)$，权值为 $16$。\n- $(4,3,1)$，权值为 $12$。\n- $(4,3,2)$，权值为 $2$。\n\n因此，样例 \\#1 的答案为 $6+16+12+2=36$。\n\n---\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1 \\le n, a_i \\le 5000$。\n\n**本题采用捆绑测试。**\n\n|子任务|$n$|特殊性质|分值|\n|-|-|-|-|\n|1|$=3$||$10$|\n|2|$\\le 300$||$20$|\n|3|$\\le 2000$||$20$|\n|4||A|$20$|\n|5|||$30$|\n\n特殊性质 A：保证 $a_i=i$。\n\n---\n\n**【提示】**\n\n本题中大部分算法都拥有较小的常数，请相信你的复杂度。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9148","tags":["数学","数论","洛谷原创","O2优化","组合数学","前缀和","洛谷月赛"],"sample_group":[["4\n1 2 3 4\n","36\n"],["6\n8 6 4 2 10 15\n","268\n"]],"created_at":"2026-03-03 11:09:25"}}