$2^x \bmod n = 1$ Again
给定正整数 $n$，求最小的使得 $2^x \bmod n = 1$ 的正整数 $x$ 或判断无解，多测，$1 \leq n \leq 2^{31} - 1$。
数学、欧拉函数、欧拉定理
首先若 $n=1$ 或 $n \bmod 2 = 0$ 则显然无解，否则由于 $\gcd(2,n) = 1$ 必定有解。
开始想二分答案，但是问题不存在单调性。值得注意的是问题存在周期性。
考虑欧拉定理，由于 $\gcd(2,n) = 1$ 有 $2^{\varphi(n)} \equiv 1 \ (\bmod \ n)$，检查 $\varphi(n)$ 的所有因数，最小的满足 $2^d \bmod n = 1$ 的因子 $d$ 即答案。
由于快速幂的时间复杂度为 $O(\log n)$，时间复杂度 $O(\sqrt{n} \log n)$，因为底数固定为 $2$ 可以应用 $O(1)$ 快速幂。
具体地，预处理模意义下 $2^0,2^1,\cdots,2^{\left\lfloor \sqrt{\varphi(n)} \right\rfloor}$ 的值和 $2^0,2^{\left\lfloor \sqrt{\varphi(n)} \right\rfloor},2^{2 \left\lfloor \sqrt{\varphi(n)} \right\rfloor}, \cdots 2^{\left\lfloor \sqrt{\varphi(n)} \right\rfloor \times \left\lfloor \sqrt{\varphi(n)} \right\rfloor}$ 的值，对于 $2^k$ 形式的幂次积如下式求解。
$$2^{\left\lfloor \frac{k}{\sqrt{\varphi(n)}} \right\rfloor} \times 2^{k \bmod \left\lfloor \sqrt{\varphi(n)} \right\rfloor}$$
注意还要预处理 $2^{\left\lfloor \sqrt{\varphi(n)} \right\rfloor + 1}$ 和 $2^{\left( \left\lfloor \sqrt{\varphi(n)} \right\rfloor +1 \right) \times \left\lfloor \sqrt{\varphi(n)} \right\rfloor}$ 的值，因为 $n$ 不一定是一个完全平方数，下取整会导致计算中某些变量的值超过 $\left\lfloor \sqrt{\varphi(n)} \right\rfloor$。
时间复杂度 $O(\sqrt{n})$。
#include<cstdio>
#include<cmath>
using namespace std;
int n,mod,phi,lim,fac[50005],facs[50005];
inline int mul(int x){return 1ll*facs[x/lim]*fac[x%lim]%mod;}
void solution(){
if(n==1||n%2==0){
printf("2^? mod %d = 1\n",n);
return;
}
mod=n,phi=n,lim=sqrt(n);
for(int i=2;i<=lim;i++) if(n%i==0){
while(n%i==0) n/=i;
phi=phi/i*(i-1);
}
if(n!=1) phi=phi/n*(n-1);
fac[0]=1,facs[0]=1,lim=sqrt(phi);
for(int i=1;i<=lim+1;i++) fac[i]=2ll*fac[i-1]%mod;
for(int i=1;i<=lim+1;i++) facs[i]=1ll*fac[lim]*facs[i-1]%mod;
for(int i=1;i<=lim;i++) if(phi%i==0&&mul(i)==1){
printf("2^%d mod %d = 1\n",i,mod);
return;
}
for(int i=lim;i>=1;i--) if(phi%i==0&&mul(phi/i)==1){
printf("2^%d mod %d = 1\n",phi/i,mod);
return;
}
}
int main(){
while(scanf("%d",&n)!=EOF) solution();
return 0;
}