【题目描述】

【输入格式】

【输出格式】

【样例输入】
2 2 47
【样例输出】
4
【数据范围】

code：

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
unsigned long long n,x,w;
void exgcd(unsigned long long a,unsigned long long b,int& x,int& y){
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,y,x);y-=(a/b)*x;
}

unsigned long long inv(unsigned long long x,unsigned long long mod){
int u,v;
exgcd(x,mod,u,v);
u=(u+mod)%mod;
return u;
}

unsigned long long multiply_64bit(unsigned long long a,unsigned long long b,unsigned long long mod){
unsigned long long ans=0,power=a;
while(b){
if(b&1){
ans+=power;
ans%=mod;
}
power<<=1;
power%=mod;
b>>=1;
}
return ans%mod;
}

unsigned long long qpow(int a,unsigned long long b,unsigned long long mod){
unsigned long long power=a,ans=1;
while(b){
if(b&1){
ans=multiply_64bit(power,ans,mod);
}
power=multiply_64bit(power,power,mod);
power%=mod;
b>>=1;
}
return ans%mod;
}

int main(){
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
cin>>n>>x>>w;
unsigned long long x1=(qpow(x,n+1,w)+n%w-multiply_64bit(n+1,x,w))%w;
unsigned long long x2=((unsigned long long)(x-1)*(x-1))%w;
unsigned long long x3=inv(x2,w);
cout<<multiply_64bit(x1,x3,w)<<endl;
return 0;
}



#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
res=0;T fh=1;char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
int mod;
struct matrix{
int a[3][3];
matrix(){memset(a,0,sizeof(a));}
int* operator [](int x){return a[x];}
matrix operator *(matrix &b){
matrix c;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%mod;
return c;
}
}S,T;
int main(){
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
lol n=gl();T[0][0]=gi();mod=gi();
S[0][1]=S[0][2]=T[1][0]=T[1][1]=T[2][1]=T[2][2]=1;
while(n){
if(n&1)S=S*T;
T=T*T;
n>>=1;
}
printf("%d",S[0][0]);
return 0;
}