[ABC228E] Integer Sequence Fair 题解

· · 题解

首先，根据乘法原理，很显然这道题的答案是 M^{\left(K^N\right)}。

本题的难点在于——如何计算这个式子。

这时，我们就需要用到著名的费马小定理：

对于一个质数 P，如果 M 不是 P 的倍数，那么 M^{P-1}\equiv 1\pmod P。

由上面的定理，易得：

M^{\left(K^N\right)}\equiv M^{\left(K^N\bmod (P-1)\right)}\pmod P

所以，本题可以使用快速幂解决。注意特判 M 是 P 的倍数的情况。

放代码：

#include<bits/stdc++.h>
#include<atcoder/all>
#define int long long
using namespace std;
const int P=998244353;
main(){
  ios::sync_with_stdio(false);
  int n,k,m; cin>>n>>k>>m;
  cout<<(m%P?atcoder::pow_mod(m,atcoder::pow_mod(k,n,P-1),P):0)<<endl; // 使用 ACL pow_mod
  return 0;
}