欢乐赛#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)