【2】做题心得 - 杂题 - 数学题【数学】【扩展欧拉定理】

· · 题解

说白了，就是 n\leq 30，a\leq 10^9 求 a^b\equiv b^a(\bmod 2^n)。

我们发现这坨东西不好处理，所以我们考虑看 a 的奇偶性。为什么这样考虑呢？因为 a\bmod 2=1 的时候有显然的答案。

a 为奇数的情况

首先我们发现此时 (a^b,2^n)=1 且 (b^a,2^n)=1。因为 a 为奇数，然后我们发现 a^b\equiv b^a。我们想要让 a^b\bmod 2^n = b^a \bmod 2^n 那么我们可以让 a^b=b^a，此时显然 b 唯一解。然后我们为了让 a^b\equiv b^a，此时 |a^b-b^a|\ge 2^n，我们发现这是不可能同余的（a\neq b）所以综上 a\bmod 2=1 时，仅存在一组 a=b 的解。

a 为偶数的情况

我们发现这时 a^b \bmod 2^n 可以为 0 仅当 2^\frac{ab}{2}\ge 2^n。所以当 b\leq n 的时候可以考虑暴力枚举（n\leq 30）否则我们发现我们需要 b^a|2^n。显然的，b 需要满足 b=k2^x，不然无法出现同余。所以，b^a=k^a2^{ax}。同时因为 2^{ax}\ge2^n，所以 ax\ge n，x\ge \lceil \frac{n}{a} \rceil 。由此可以推出 b^a=k^a2^{ax- \lceil \frac{n}{a} \rceil}2^{ \lceil \frac{n}{a} \rceil} 。这看起来很复杂，但是我们知道了 n< k^a2^{ax- \lceil \frac{n}{a} \rceil}2^{ \lceil \frac{n}{a} \rceil}\leq 2^n。我们就发现 \frac{n}{2^{ \lceil \frac{n}{a} \rceil}}<k^a2^{ax- \lceil \frac{n}{a} \rceil}\le \frac{2^n}{2^{ \lceil \frac{n}{a} \rceil}}。这里的 k^a2^{ax- \lceil \frac{n}{a} \rceil} 没有了约束，那么这个东西的整数解数量就是答案。

具体的，我们设 y=\lceil \frac{n}{a} \rceil，并预处理出 n\leq 50 时 2^n 的值 mul_n（防止越界）然后我们直接计算 mul_{n-y}-\lfloor \frac{n}{mul_y}\rfloor，输出即可。

最终总结

这道题我们通过分类 a 的值，归纳出了 b 的取值范围，求出了 a^b\equiv b^a(\bmod 2^n) 的答案。当然要是你觉得过于复杂，可以考虑通过其他的方法直接求出 b\ge n 的范围。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,n,ans,mul[55];
int qp(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)
            res=(res*a)%p;
        a=(a*a)%p,b>>=1;
    }
    return res;
}
signed main(){
    mul[0]=1;
    for(int i=1;i<=50;i++)
        mul[i]=mul[i-1]*2;
    int T;
    cin>>T;
    while(T--){
        cin>>a>>n;
        if(a&1)
            cout<<1<<"\n";
        else{
            ans=0;
            for(int b=1;b<=n;b++)
                if(qp(a,b,mul[n])==qp(b,a,mul[n]))
                    ++ans;
            int y=n/a+bool(n%a);
            ans+=mul[n-y]-n/mul[y];
            cout<<ans<<"\n";
        }
    }   
    return 0;
}