马上区域赛网络赛了，整理了一些公式，本题是一个公式的模板题。 公式：
gac(am−bm,an−bn)=agcd(m,n)−bgcd(m,n) 公式变形： gcd(am−1,an−1)=agcd(m,n)−1 直接套公式做就好了 code： #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> #include<string> #include <set> //a&3==a%4 using namespace std; #define ll long long #define mem(a) memset(a,0,sizeof(a)) const double eps=1e-8; const int maxn=30010;//须填写 const int inf=0x3f3f3f3f; int read() { //输入外挂 int res = 0; bool flag =false; char ch; if((ch = getchar()) == '-') flag = true; else if(ch >= '0' && ch <= '9') res = ch - '0'; while((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0'); return flag ? -res : res; } int mod; int gcd(int x,int y) { if(y==0) return x; else return(gcd(y,x%y)); } int quickpow(int a,int b) { int ans=1; while(b) { if(b&1) { ans=(ans*a)%mod; b--; } b=b>>1; a=(a*a)%mod; } ans=ans%mod; return ans; } int main() { int kase; int a,m,n; kase=read(); while(kase--) { a=read(); m=read(); n=read(); mod=read(); int pow=gcd(m,n); int res=(quickpow(a,pow)+mod-1)%mod;//这里要处理一下，不然可能出现负数 // cout<<pow<<endl; cout<<res<<endl; } return 0; } //寇瑟茹酒