{"problem":{"name":"BZOJ4833 最小公倍佩尔数","description":{"content":"令 $(1+\\sqrt{2})^n=e(n)+\\sqrt{2}f(n)$，其中 $e(n),f(n)$ 都是整数，显然有 $(1-\\sqrt{2})^n=e(n)-\\sqrt{2}f(n)$。令 $g(n)=\\operatorname{lcm}(f(1),f(2),\\dots,f(n))$。 给定两个正整数 $n,p$，其中 $p$ 是质数，并且保证 $f(1),f(2),\\dots,f(n)$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10663"},"statements":[{"statement_type":"Markdown","content":"令 $(1+\\sqrt{2})^n=e(n)+\\sqrt{2}f(n)$，其中 $e(n),f(n)$ 都是整数，显然有 $(1-\\sqrt{2})^n=e(n)-\\sqrt{2}f(n)$。令 $g(n)=\\operatorname{lcm}(f(1),f(2),\\dots,f(n))$。\n\n给定两个正整数 $n,p$，其中 $p$ 是质数，并且保证 $f(1),f(2),\\dots,f(n)$ 在模 $p$ 意义下均不为 $0$，请计算 $\\sum \\limits_{i=1}^n i\\times g(i)$ 模 $p$ 的值。\n\n## Input\n\n第一行包含一个正整数 $T$，表示有 $T$ 组数据。\n\n接下来是测试数据。每组测试数据只占一行，包含两个正整数 $n$ 和 $p$。\n\n## Output\n\n对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。\n\n[samples]\n\n## Background\n\n题目来自 BZOJ 2017 年 4 月月赛。\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\leq T\\leq 210$，$1\\leq n\\leq 10^6$，$2\\leq p\\leq 10^9+7$，$\\sum n\\leq 3\\times 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10663","tags":["数论","O2优化","莫比乌斯反演","容斥原理"],"sample_group":[["5\n1 233\n2 233\n3 233\n4 233\n5 233","1\n5\n35\n42\n121"]],"created_at":"2026-03-03 11:09:25"}}