題目大意

給定兩個數 $a, m$ ，求滿足 $a^u \equiv u (mod\ \ m)$ 的一個解。
$(1\leq a,m \leq10^9 ,0\leq u\leq 10^{18})$

題解

參考了討論區 https://blog.nowcoder.net/n/576f9463036346f0a0fb04fee50fac75 的方法

求解

考慮使用歐拉定理，考慮 $b>=\phi_p$ 的情況。
$a^u\equiv\begin{cases}a^{u\% \phi_m }&gcd(a,u)=1\\a^{u\% \phi_i+\phi_m}& gcd(a,u)!=1\end{cases}(mod \ m)$
定義 $d=u\%\phi_m$ 或 $u\%\phi_m+\phi_m$ 和
$k*\phi_p+d=u(k>=0)$
則原式可以轉化為 $a^d \equiv d+k*\phi_m (mod\ m)$
移項可以得到 $a^d-d\equiv k*\phi_m(mod\ m)$
$\phi_m*x1+m*y1\equiv gcd(\phi_m,m) (mod \ m)$ 是一個已知有解的同余方程
回到上一個方程想要得到解 $k$ ，顯然要滿足 $a^d-d=x *gcd(m,\phi_m),(x>0)$
也就是 $a^d \equiv d (mod \ gcd(m,\phi_m))$ 。
重新得到了題目，但是模數縮小了，因此我們想到了遞歸，直到模數為 $1$ 時直接推出答案。

回溯

假設我們已經得到了最后一組解 $d = 0$ ，
求解同余方程 $a^d-d\equiv k*\phi_m(mod\ m)$ ，使用擴展歐幾里得定理，推出 $x 1$ 的值，
$k=x1*\frac{a^d-d}{gcd(m,\phi_m)}\%mod$
由于 $a^d$ 超出范圍，根據 $\frac{a}{b}\%(b*c)=\frac{a\%(b*c)}{b}$ 得出
$k=x1*(a^d-d)\%m/\phi_m$ 。
再利用 $k*\phi_p+d=u$ ，得出結果即可。

參考代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll phi(ll x)
{ll ans=x;for(int i=2;i*i<=x;i++){if(x%i==0)ans=ans/i*(i-1);while(x%i==0)x/=i;}if(x!=1)ans=ans/x*(x-1);return ans;
}
ll ksm(ll a,ll b,ll p)
{ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(!b){x=1,y=0;return a;}ll k=exgcd(b,a%b,y,x);y-=a/b*x;return k;
}
int n,T;
ll a,m;
ll work(ll a,ll p)              //遞歸求解
{if(p==1)return 0;ll m=phi(p);ll b=work(a,__gcd(m,p))+m;ll x,y;ll d=exgcd(m,p,x,y);ll k=(((x*(ksm(a,b,p)-b+p))%p+p)%p/d);   //回溯求值return k*m+b;
}
int main()
{cin>>T;while(T--){scanf("%lld%lld",&a,&m);printf("%lld\n",work(a,m));}
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/38058.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/38058.shtml
英文地址，請注明出處：http://en.pswp.cn/news/38058.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！