B Semi-Puzzle: Brain Storm

题目大意

给定a和p，求满足$a^u=u(p)a^u=u\; \backslash \; (p)$的u

解题思路

注：以下的等号皆为同余号，不是真正的等号!$\backslash \backslash$ 考虑欧拉定理，因为$a^u=a^{u\mathrm{\%}\phi (p))}a^u=a^\{u\; \backslash \%\; \backslash varphi(p))\}$,所以假设存在一个u满足题意，则有$a^u=a^{u\mathrm{\%}\phi (p))}=a^j=j+k\ast \phi (p)a^u=a^\{u\; \backslash \%\; \backslash varphi(p))\}=a^j=j+k*\backslash varphi(p)$,其中$j=u\mathrm{\%}\phi (p),k>=0j=u\; \backslash \%\; \backslash varphi(p),k>=0$,所以如果我们考虑枚举$jj$从$00$到$\phi (p)-1\backslash varphi(p)-1$，那么对于每一个j，只需要判断是否存在一个大于等于0的k满足$a^j=j+k\ast \phi (p)a^j=j+k*\backslash varphi(p)$,把$a^j-ja^j-j$看做c，$\phi (p)\backslash varphi(p)$看作a，所以就变成了判断是否存在一个k满足$ak=c(\phi (p))ak=c\backslash \; \backslash \; (\backslash varphi(p))$，这显然是一个线性同余方程，而方程有解的情况就是$gcd(\phi (p),p)\mathrm{\mid }(a^j-j)gcd(\backslash varphi(p),p)|(a^j-j)$,而题目保证有解，所以我们只需要考虑什么j可以满足$a^j=j(gcd(\phi (p),p))a^j=j\backslash \; \backslash \; (gcd(\backslash varphi(p),p))$，显然就变成了原问题的一个子问题，所以我们递归解决，当模数为1时返回0即可。现在我们已经求出了j，而我们要的应该是满足题意的u，即$u=j+k\ast \phi (p)u=j+k*\backslash varphi(p)$,所以将递归得到的j套入同余方程中得到k，最后算出u即可。

细节问题

注意a和p和互质问题，当a和p不互质时欧拉定理要加上$\phi (p)\backslash varphi(p)$，求解关于k的同余方程时因为$a^{j}a^j$很大，不能直接算出来，所以在快速幂算的时候注意$\frac{a\mathrm{\%}(b\ast c)}{b}=\frac{a}{b}\mathrm{\%}c\backslash frac\{a\backslash \%(b*c)\}\{b\}=\backslash frac\{a\}\{b\}\; \backslash \; \backslash \%c$这个式子就行

参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e8;
int phi(int x){
    int res=x;
    for(int i=2;i<=x/i;i++){
        if(x%i==0)res=res/i*(i-1);
        while(x%i==0)x/=i;
    }
    if(x!=1)res=res/x*(x-1);
    return res;
}
int exgcd(int a, int b, int& x, int& y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int qmi(int a,int b,int p){
    int res=1;
    a%=p;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int huang(int a,int p){
    if(p==1)return 0;
    int m=phi(p);
    int j=huang(a%__gcd(m,p),__gcd(m,p));
    j+=m;
    int x,y;
    int d=exgcd(m,p,x,y);
    int mod=p/d;
    int ans=0;
    ans=(((x*(qmi(a,j,mod*d)-j+mod*d))%(mod*d)+(mod*d))%(mod*d)/d);
    return ans*m+j;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int a,m;
        cin>>a>>m;
        int ans=huang(a,m);
        cout<<ans<<endl;
    }
}