题解 | 萌新向D 题题解

萌新联赛D

要记得开 $longlonglong\; long$ 不然通过率 $\mathrm{\%}0\backslash \%0$ !

方法一 多观察

由次可以从 $22$ 开始每次乘以它本身 循环 n 次即可得出答案

参考代码

#include<iostream>
using namespace std;

#define int long long
signed main(){
    int n,p; cin >> n >> p;
    int  t = 2;
    while(n--){
        t = t*t;
        t %= p;
    }
    cout << t << '\n';
}

方法二 欧拉定理：

定理内容

其中 $\varphi \backslash phi$ 是欧拉函数

然后加上快速幂求即可算出答案。

参考代码

#define int long long
 
typedef pair<int, int> pair_;
 
int euler(int n){
    int res = n;
    for(int i =2; i <=n/i; i++){
        if(n % i == 0){
            res = res/i*(i-1);
            while(n % i == 0){
                n/= i;
            }
        }
    }
    if(n > 0) res = res/n*(n-1);
    return res;
}
 
int quick_pow(int a,int b,int p){
    int res = 1 % p;
    while(b){
        if(b & 1){
            res = res * a % p;
        }
        a = a*a%p;
        b >>= 1;
    }
    return res;
}
void solve(){
    int n,p; cin >> n >> p;
    int mod = euler(p);
    int pow = quick_pow(2,n,mod);
    int res = quick_pow(2,pow,p);
    cout << res << '\n';
}