AT_tenka1_2017_f

· · 题解

一个很妙的数论题，feecle6418 过来讲课的时候讲的，思路还是很有参考价值的，写篇题解记录一下。

主要是另外两篇题解都有点让人迷糊，有幂塔的那篇感觉不咋清楚，yangchenxiao 的那篇感觉少一点推理过程，我就想写一篇清楚一点的，把这个题思考的过程给写清楚，也算是对 yangchenxiao 题解的补充，毕竟这个题代码很简单主要就是怎么想出来的比较难。

以下推导过程中 a 是题面中的 A，x 是 K，p 是 M。

思路

首先看到 a^x\equiv x\pmod p 这个诡异的式子我们考虑怎么列出同余方程求解，但是这里只有一个式子的限制，我们珂以考虑设一个 u 满足 a^x\equiv x\equiv u\pmod p。

这样子珂以自然得出两个式子 x\equiv u\pmod p 和 a^x\equiv u\pmod p，而对于后者珂以考虑将 x 从指数变成底数，根据扩展欧拉定理可得 x\equiv Q\pmod{\varphi(p)}，Q 是我们设的满足这个式子的一个数。

我们珂以假使这个 Q 就直接是 \log_a u，即 x\equiv \log_a u\pmod{\varphi(p)}，我们就能和前面的 x\equiv u\pmod p 一起得出一个新式子：u\equiv \log_a u\pmod{\gcd(p,\varphi(p))}，接着就能得到 a^u\equiv u\pmod{\gcd(p,\varphi(p))}。

虽然 x\equiv \log_a u\pmod{\varphi(p)} 是不一定成立的，但这个是不影响我们主要思路的，你珂以把 \log_a u 只看成一个记号。

这个时候我们发现这个 a^u\equiv u\pmod{\gcd(p,\varphi(p))} 的形式和最开始的是一样的，我们便珂以将这个式子和最开始的式子结合便可得出两个式子：x\equiv a^u\pmod p,x\equiv u\pmod{\varphi(p)}。

这也就是那篇题解中的 A^y\equiv x\pmod m,x\equiv y\pmod{\varphi(m)}，那么接下来就和那片题解差不多了。如果 A^y\equiv y\pmod{\varphi(m)}，则有 x\equiv A^y\pmod{\rm{lcm}(m,\varphi(m))}，珂以递归进行求解。

还有就是一个有趣的地方 x 比较小的时候确实不能保证欧拉定理能成立，但是经过我实测，这个题不需要取那个 100 的下界，甚至只要 x 不是 0 就能过这个题，而且我看到很多人都取了那个 100，连官方题解里面都是这个数，我也不知道为什么，有人知道的话教教我呗。

还有注意运算会非常大，你要么用龟速乘要么开 ___int128，要不然只有 long long 会爆。

代码实现珂以看看，思路更重要，其实感觉用扩欧解同余方程似乎直观一点。

code

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
const ll N=2*114514,M=1919810;
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
ll T,ans,a,p,pm;
ll qpow(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll calc_phi(ll n){
    if(n==1) return 1;
    ll phi=n;
    for(int i=2;i<=sqrtl(n);++i){
        if(n%i==0) phi=phi/i*(i-1);
        while(n%i==0) n/=i;
    }
    if(n>1) phi=phi/n*(n-1);
    return phi;
}
ll solve(ll a,ll p){
    if(p==1) return 1; //面白い
    ll pm=calc_phi(p),gcd=__gcd(p,pm);
    ll lcm=p*pm/gcd,u=solve(a,pm),ans;
    ans=qpow(a,u,lcm);
    if(ans<1) ans+=lcm;//不是0就行了 
    return ans;
}
int main(){
    T=read();
    while(T--){
        ans=0;
        a=read(),p=read();
        if(a==0){ //这两个特判很简单 
            write(p),putchar('\n');
            continue;
        }
        if(a==1){
            printf("1\n");
            continue;
        }
        write(solve(a,p)),putchar('\n');
    }
    return 0;
}

其实这个题我还是有个地方不懂，就是 feecle6418 来讲课的时候他是推出了 a^u\equiv u\pmod{\gcd(p,\varphi(p))} 然后写出了 x\equiv a^u\pmod p,x\equiv u\pmod{\varphi(p)} 就说珂以解两个同余方程然后就可以一层一层递归了，但是 yangchenxiao 的题解说的是 A^y\equiv y\pmod{\varphi(m)}，我也试了把这个给改了但是只能过十九个点，就这里不太想地通，如果有人知道我是哪里推错了还请教教我啊。