欢乐赛#40 | T3题解

T3:

这一题因为 $n$ 最大可以达到 $10^6$，如果直接计算 $114514^n$ 再取模，数值会非常大，计算会非常慢。所以我们要使用快速幂^[1]进行计算。

C++代码：

#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long s = 1, d = 114514;
    while(n > 0){
        if(n % 2 == 1){
            s *= d;
            s %= 998244353;
        }
        d *= d;
        d %= 998244353;
        n /= 2;
    }
    cout << s;
    return 0;
}

Python代码：

n = int(input())
s = 1
d = 114514
while n > 0:
    if n % 2 == 1:
        s *= d
        s %= 998244353
    d **= 2
    d %= 998244353
    n //= 2
print(s)

---

1. 快速幂的基本思想是利用二分的方式计算幂次，通过将指数不断减半来减少乘法次数，从而降低时间复杂度。
   我们使用如下步骤进行计算：
   首先设定初始值 $s = 1$，$d = 114514$。
   其次通过二进制拆解指数 $n$，如果当前位为 1，则将 $s$ 乘上当前的底数 $d$ 并与 $998244353$ 取模；
   然后每次将 $d$ 平方，同时对 $998244353$ 再次进行取模，使得数值不会过大；
   最后将 $n$ 右移一位，继续计算，直到 $n = 0$。 ↩︎