{"problem":{"name":"[HUSTFC 2023] Fujisaki 讨厌数学","description":{"content":"众所周知，Fujisaki 在微积分（一）（上）、微积分（一）（下）、线性代数、离散数学（一）、概率论与数理统计这些课程中，只取得了非常低的分数，这导致他十分痛恨高等数学，因此他给大家带来了一道初等数学题。 已知 $x+x^{-1}=k$，其中 $k$ 是一个整数且 $k\\ge 2$，Fujisaki 想让你帮他求出 $x^n+x^{-n}$ 的值。可以证明对于任意的整数 $n \\ge 0$，这","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9777"},"statements":[{"statement_type":"Markdown","content":"众所周知，Fujisaki 在微积分（一）（上）、微积分（一）（下）、线性代数、离散数学（一）、概率论与数理统计这些课程中，只取得了非常低的分数，这导致他十分痛恨高等数学，因此他给大家带来了一道初等数学题。\n\n已知 $x+x^{-1}=k$，其中 $k$ 是一个整数且 $k\\ge 2$，Fujisaki 想让你帮他求出 $x^n+x^{-n}$ 的值。可以证明对于任意的整数 $n \\ge 0$，这个值都是一个整数。由于结果可能会非常大，你只需要求出其对 $M$ 取模后的值。\n\n## Input\n\n一行包含三个整数 $M\\ (3\\le M\\le 998\\,244\\,353)$，$k\\ (2\\le k<M)$ 和 $n\\ (0\\le n\\le 10^{18})$，其含义如题目所述。\n\n## Output\n\n输出一个整数，表示答案对 $M$ 取模后的值。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9777","tags":["2023","O2优化","矩阵加速","高校校赛"],"sample_group":[["998244353 10 1\n","10"],["998244353 2 3\n","2"],["100 4 5\n","24"]],"created_at":"2026-03-03 11:09:25"}}