{"problem":{"name":"[LMXOI Round 1] Dreamer","description":{"content":"定义积性函数 $f(n)=(\\mu \\ast\\operatorname{Id_2})(n)$。 给定 $n,k$，你需要求出  $$\\sum_{i_1\\mid n}\\sum_{i_2\\mid i_1}\\cdots\\sum_{i_k\\mid i_{k-1}}f(i_k)i_1i_k\\mu^2\\left(\\dfrac{i_1}{i_k}\\right)$$ #### Tips： $\\mu$ 表示","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":30720},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10117"},"statements":[{"statement_type":"Markdown","content":"定义积性函数 $f(n)=(\\mu \\ast\\operatorname{Id_2})(n)$。\n\n给定 $n,k$，你需要求出 \n\n$$\\sum_{i_1\\mid n}\\sum_{i_2\\mid i_1}\\cdots\\sum_{i_k\\mid i_{k-1}}f(i_k)i_1i_k\\mu^2\\left(\\dfrac{i_1}{i_k}\\right)$$\n\n#### Tips：\n\n$\\mu$ 表示莫比乌斯函数。\n\n关于 $f$，$f(n)=\\displaystyle \\sum_{d\\mid n}\\mu(d)\\left(\\dfrac{n}{d}\\right)^2$。\n\n## Input\n\n本题有多组数据，第一行输入一个正整数 $T$，表示数据组数。\n\n考虑到 $n$ 很大，所以我们会给出 $n$ 的标准质因子分解 $n=\\displaystyle \\prod_{i=1}^t p_i^{\\alpha_i}$。\n\n对于每一组询问，我们首先给出两个整数 $k,m$。\n\n第二行给出 $t$，下面 $t$ 行每行两个整数表示 $p_i,\\alpha_i$。\n\n（保证 $p_i\\ge p_{i-1},i\\ge 2$，$\\alpha_i\\ge 1$）。\n\n## Output\n\n对于每个询问，输出一行表示答案 $\\mod m$ 的值。\n\n[samples]\n\n## Background\n\n[加强版链接](https://www.luogu.com.cn/problem/U402756)。\n\n这是一道数学题，可是 LMX 给 HQZ 出的。\n\n## Note\n\n对于 $100\\%$ 的数据，有 $T \\le 20,n\\le 10^{24},1\\le k\\le 10^6,m\\le 1.14\\times 10^9$。\n\n| 测试点编号 |      $n$      |    $k$     |   $T$    | 特殊性质 |\n| :--------: | :-----------: | :--------: | :------: | :------: |\n|    $1$     |   $\\le 80$    |  $\\le 4$   | $\\le 5$  |   $N$    |\n|    $2$     |  $\\le 10^6$   |  $\\le 10$  | $\\le 5$  |   $N$    |\n|    $3$     | $\\le 10^{12}$ |  $\\le 20$  | $\\le 20$ |   $N$    |\n|    $4$     | $\\le 10^{18}$ |  $\\le 1$   | $\\le 20$ |   $N$    |\n|    $5$     | $\\le 10^{18}$ | $\\le 10^3$ | $\\le 20$ |   $N$    |\n|    $6$     | $\\le 10^{18}$ | $\\le 10^5$ | $\\le 20$ |   $A$    |\n|    $7$     | $\\le 10^{18}$ | $\\le 10^6$ | $\\le 20$ |   $B$    |\n|    $8$     | $\\le 10^{24}$ | $\\le 10^6$ | $\\le 20$ |   $B$    |\n|    $9$     | $\\le 10^{24}$ | $\\le 10^6$ | $\\le 20$ |   $C$    |\n|    $10\\sim20$    | $\\le 10^{24}$ | $\\le 10^6$ | $\\le 20$ |   $N$    |\n\n性质 $A$：保证 $t\\le 10$。\n\n性质 $B$：保证 $n$ 的质因子分解 $\\displaystyle\\prod_{i=1}^t p_i^{\\alpha_i}$ 中 $\\alpha_i=1$。\n\n性质 $C$：$m$ 是素数，且保证 $\\gcd(n,m)=1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10117","tags":["数论","O2优化"],"sample_group":[["5\n3 998244353\n3\n3 2\n5 1\n7 1\n4 1000000009\n2\n2 1\n3 2\n1 998244353\n2\n2 2\n3 1\n11451 191981012\n11\n2 1\n3 1\n5 1\n7 1\n11 1\n13 1\n17 1\n19 1\n23 1\n29 1\n31 1\n514 520\n2\n2 10\n3 10","189282114\n124678\n14965\n82966193\n260\n"]],"created_at":"2026-03-03 11:09:25"}}