2023牛客暑期多校训练营9 B.Semi-Puzzle: Brain Storm

题目大意

给定两个数 $a,m$ ，求满足 $a^u\equiv u(modm)$ 的一个解。
$(1\le a,m\le 10^9,0\le u\le 10^{18})$

题解

参考了讨论区 https://blog.nowcoder.net/n/576f9463036346f0a0fb04fee50fac75 的方法

求解

考虑使用欧拉定理，考虑 $b>={\varphi }_p$的情况。
$a^u\equiv \{\begin{array}{ll}{a}^{u\%{\varphi }_m}& gcd(a,u)=1\\ a^{u\%{\varphi }_i+{\varphi }_m}& gcd(a,u)!=1\end{array}(modm)$
定义 $d=u\%{\varphi }_m$ 或 $u\%{\varphi }_m+{\varphi }_m$ 和
$k\ast {\varphi }_p+d=u(k>=0)$
则原式可以转化为 $a^d\equiv d+k\ast {\varphi }_m(modm)$
移项可以得到 $a^d-d\equiv k\ast {\varphi }_m(modm)$
${\varphi }_m\ast x1+m\ast y1\equiv gcd({\varphi }_m,m)(modm)$ 是一个已知有解的同余方程
回到上一个方程想要得到解 $k$ ，显然要满足 $a^d-d=x\ast gcd(m,{\varphi }_m),(x>0)$
也就是 $a^d\equiv d(modgcd(m,{\varphi }_m))$。
重新得到了题目，但是模数缩小了，因此我们想到了递归，直到模数为 $1$ 时直接推出答案。

回溯

假设我们已经得到了最后一组解 $d=0$ ，
求解同余方程 $a^d-d\equiv k\ast {\varphi }_m(modm)$，使用扩展欧几里得定理，推出 $x1$ 的值，
$k=x1\ast \frac{a^d-d}{gcd(m,{\varphi }_m)}\%mod$
由于 $a^d$ 超出范围，根据 $\frac{a}{b}\%(b\ast c)=\frac{a\%(b\ast c)}{b}$得出
$k=x1\ast (a^d-d)\%m/{\varphi }_m$ 。
再利用 $k\ast {\varphi }_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));}
}