yicongli

Gym 101848D

Jan 23rd, 2021
744
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. inline ll qpow(ll a,ll b,int p){
  17.     a%=p;
  18.     ll ans=1;
  19.     while(b){
  20.         if(b&1)(ans*=a)%=p;
  21.         (a*=a)%=p;
  22.         b>>=1;
  23.     }
  24.     return ans;
  25. }
  26.  
  27. inline int sub(ll a,ll b,int p){
  28.     a=(a-b)%p;
  29.     return a<0?a+p:a;
  30. }
  31.  
  32. int main(){
  33.     // freopen(".in","r",stdin);
  34.     // freopen(".out","w",stdout);
  35.     ll n,k,p;r(n),r(k),r(p);
  36.     if(p==2){
  37.         printf("%d\n",k==0);
  38.         return 0;
  39.     }
  40.     printf("%d\n",sub(qpow(2,sub(qpow(2,n,p-1),n,p-1),p),k==0,p));
  41.     return 0;
  42. }
RAW Paste Data