题解:
当 p 不等于 2 时,我们可以想到的是
这里给出指数节公式
根据公式
综上
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,k,p; ll mut(ll a,ll b,ll mod) { ll ans = 0; while(b) { if(b & 1) ans = (ans + a) % mod; a = (a + a) % mod; b >>= 1; } return ans; } ll power(ll a,ll b,ll mod) { a %= mod; ll ans = 1; while(b) { if(b & 1) ans = mut(ans,a,mod); a = mut(a,a,mod); b >>= 1; } return ans; } ll phi(ll n) { ll ans = n; for(ll i = 2;i*i<=n;i++) { if(n % i == 0) { ans = ans - ans / i; while(n % i == 0) n /= i; } } if(n > 1) ans = ans - ans / n; return ans; } ll inv(ll a,ll mod) { return power(a,mod-2,mod)%mod; } int main() { while(~scanf("%lld%lld%lld",&n,&k,&p)) { ll ans = 0; if(p != 2) { ll phip = phi(p); ll a = power(2,n,phip) + phip; a = power(2,a,p); ll b = power(2,n,p); ans = a * inv(b,p) % p; if(!k) ans--; ans = (ans % p + p) % p; } else { ans = 0; if(!k) ans = 1; } printf("%lld\n",ans); } return 0; }