[HUSTFC 2023] Fujisaki 讨厌数学

Luogu
IDLGP9777
Time1000ms
Memory256MB
DifficultyP4
2023O2优化矩阵加速高校校赛
众所周知,Fujisaki 在微积分(一)(上)、微积分(一)(下)、线性代数、离散数学(一)、概率论与数理统计这些课程中,只取得了非常低的分数,这导致他十分痛恨高等数学,因此他给大家带来了一道初等数学题。 已知 $x+x^{-1}=k$,其中 $k$ 是一个整数且 $k\ge 2$,Fujisaki 想让你帮他求出 $x^n+x^{-n}$ 的值。可以证明对于任意的整数 $n \ge 0$,这个值都是一个整数。由于结果可能会非常大,你只需要求出其对 $M$ 取模后的值。 ## Input 一行包含三个整数 $M\ (3\le M\le 998\,244\,353)$,$k\ (2\le k<M)$ 和 $n\ (0\le n\le 10^{18})$,其含义如题目所述。 ## Output 输出一个整数,表示答案对 $M$ 取模后的值。 [samples]
Samples
Input #1
998244353 10 1
Output #1
10
Input #2
998244353 2 3
Output #2
2
Input #3
100 4 5
Output #3
24
API Response (JSON)
{
  "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$,这...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments