2023牛客暑期多校訓練營9-B Semi-Puzzle: Brain Storm

https://ac.nowcoder.com/acm/contest/57363/B

題意

解題思路

歐拉定理
$$a^b\equiv ?\begin{array}{llc}& a^{b\%\phi (p)}& gcd(a,p)=1\\ & a^b& gcd(a,p)\ne 1,b<\phi (p)\\ & a^{b\%\phi (p)+\phi (p)}& gcd(a,p)\ne 1,b\ge \phi (p)\end{array}$$
$$\begin{array}{c}{a}^u\equiv u(\mathrm{mod}p)\\ 設d=u\%\phi (p)+\phi (p)\\ u=d+k\phi (p)\\ a^{d+k\phi (p)}\equiv d+k\phi (p)(\mathrm{mod}p)\\ a^d?d\equiv k\phi (p)(\mathrm{mod}p)\end{array}$$
將取余打開，可得：
$$\begin{array}{c}\phi (p)x+py=a^d?d\end{array}$$
顯然可以用擴展歐幾里得求解當$\phi (p)x+py=\gcd (p,?(p))$的解，為保證$d$有解，故$\gcd (p,\phi (p))\mid a^d?d$，設$a^d?d=h\gcd (\phi (p),p)$，故$a^d=h\gcd (\phi (p),p)+d$，可以發現$a^d\equiv d(\mathrm{mod}\gcd (\phi (p),p))$，可以發現形式上與$a^u\equiv u(\mathrm{mod}p)$，顯然當$p=1$時，$u=0$，有了邊界條件，可以遞歸求出$u$。$u=d+k\phi (p)$，$k$即為$\phi (p)x+py=a^d?d$中$x$的解，當求出$\phi (p)x_0+p{y}_0=\gcd (p,?(p))$:
$$\begin{array}{cc}x=& x_0\times (\frac{a^d?d}{\gcd (\phi (p),p)}\%p)\\ =& x_0\times (\frac{(a^d?d)\%p}{\gcd (\phi (p),p)})\end{array}$$

代碼

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
ll T,a,m;
ll phi(ll n){ll sum=n;for(ll i=2;i*i<=n;i++){if(n%i==0){while(n%i==0)n/=i;sum/=i,sum*=i-1;}}if(n>1)return sum/n*(n-1);return sum;
}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1,y=0;return a;}ll v=exgcd(b,a%b,y,x);y-=a/b*x;return v;
}
ll power(ll x,ll p,ll mod){ll res=1;while(p){if(p&1)res*=x,res%=mod;x*=x,x%=mod;p>>=1;}return res;
}
ll dfs(ll a,ll p){if(p==1)return 0;ll ph=phi(p);ll x,y;ll v=exgcd(ph,p,x,y);x=(x%p+p)%p;ll d=dfs(a,v)+ph;return d+(x*((power(a%p,d,p)-d%p+p)%p/v)%p)*ph;
}
void solve(){cin>>a>>m;ll x=dfs(a,m);cout<<x<<'\n';
}
int main(){cin>>T;while(T--)solve();
}