Order and primitive root and exponential equations(阶、原根和指数方程)
一、概念
1、阶
阶：\(a^x ≡1 (\bmod m)\)上面的x就是阶
2、原根
\(\bmod m\)的阶为\(\phi(m)\)的数
3、指数方程(BSGS)
BSGS(baby step giant step)
不暴力的解\(a^x ≡ b (\bmod m)\)
二、阶
1.理解
如果\((a,m) = 1\)，那么记\(x\)为最小的正整数使得\(a^x ≡ 1(\bmod m)\)
\(x|\phi(m)\)，反证法。
阶可以理解为循环长度的是多少。
我们不停的乘a模\(m\)，看看循环长度是多少，我们绕着循环走，走\(\phi(m)\)步一定会走回原来的地方。最小的正整数\(x\)使得\(a^x ≡ 1(\bmod m)\),\(x\)称为\(a \bmod m\)的阶。
eg.a = 2,m = 7
1 ——>2——>4
↑———3————|
eg2.a = 3,m = 7
1 ——>3——>2 ——>6——>4——>5
↑————————6——————————|
2.求阶
那么我们怎么去求这个阶呢？
1.(纯暴力)因为我们知道\(\phi(m)\)步只会一定会循环，那我们从1 for 到\(\phi(m)\)看看最小的是多少。
2.阶|\(\phi(m)\)，我们枚举\(\phi(m)\)的所有因子去找到最小的\(a \mod m = 1\)
3.(正解)我们求阶的时候可以从\(\phi(m)\)开始依次除掉每个因子判断。
\(\phi(m) = p1^{e1}p2^{e2}...pk^{ek}\)
\(d = \phi(m)\) \(a^d \bmod m = 1\)
for(每个因子pi){
while(\(d\)%\(pi==0\)&&\(a^{\frac{d}{pi}}\)% \(m == 1\)){
d/=pi
}
}
最后的这个d就是答案
eg. a = 9,m = 31,\(\phi(m)=30=2\times3\times5\)
一开始，令\(d = \phi(m) = 30\)
对于因子\(2\)，d有2这个因子，再看d能不能把2这个因子除掉，那\(d = \dfrac{\phi(m)}{2} = \dfrac{30}{2} = 15\)，去看\(a^{15} \bmod m\)是不是等于1的，是的话就把d除掉2这个因子，d = 15，接着看3这个因子，我们发现\(a^5 \bmod m != 1\)所以\(3\)这个因子不能被除掉。因为我们始终要保证\(a^d \bmod m == 1\)
\(pi = 2\) \(a^{15} \bmod m = 1\) ,d = 15
\(pi = 3\) \(a^{5} \bmod m = 1?\)不行
\(pi = 5\) \(a^{3} \bmod m = 1?\)不行
所以这里a mod m的阶是15。
\(\phi(m) = p1^{e1}p2^{e2}...pk^{ek}\)
\(ord = p1^{a1}p2^{a2}...pk^{ak}\)
从\(\phi(m)到ord\)
比如上述例子：
\(\phi(m) = 2^{1}3^{1}5^{1}\)
\(ord = 2^{0}3^{1}5^{1}\)
例题：
阶
给定素数p，回答T(1e5)个询问。
给定一个a，问最小的正数x满足ax≡1(mod p)。
#include
using namespace std;
typedef long long ll;
const int N = 1010;
int pf[N],t;
ll ksm(ll a,ll b,ll mod)
{
ll ans = 1,base = a;
while(b)
{
if(b&1)
{
ans = ans*base;
ans%=mod;
}
base = base*base;
base%=mod;
b>>=1;
}
return ans;
}
int main()
{
int p,T;
cin>>p>>T;
int m = p-1;
for(int i = 2;i*i<=m;i++)
{
if(m%i==0)
{
pf[t++] = i;
while(m%i==0)m/=i;
}
}
if(m!=1)
pf[t++] = m;
for(int i = 1;i<=T;i++)
{
int a;
cin>>a;
int d = p-1;
for(int i = 0;i while(d%pf[i]==0&&ksm(a,d/pf[i],p)==1)//pf[i]是d的因子，且a^{d/pf[i]} mod p == 1说明这个因子可以被除掉 d/=pf[i]; cout< } return 0; } 三、原根(useful) 1.理解 如果\(g (\bmod m)\)的阶为\(\phi(m)\),那么\(g\)为\(m\)的原根。 阶是在互质数 (a,m)间的定义：满足 \(a^n≡1(\bmod m)\) 的最小 n 被称作 a 模 m 的阶 明显，在 a,m 不互质时，a 的无论多少次幂全都是 \(\gcd(a,m)\)的倍数，故不可能取到 1； 而当互质时，依据扩展欧拉定理，必有 \(a^{\phi(m)}≡1(\bmod m)\)，但也不排除存在更小的 \(n\)。它未必是最小的，所以不一定是阶，而当\(\phi (m)是a模m\)的阶时，我们称a为m的一个原根。 \(g^0,g^1...g^{\phi(m)}\)构成了模\(m\)的简化剩余系。 只有\(1,2,4,p^a,2p^a\)存在原根(这里的\(p\)的奇素数) 结论(记一下):奇素数的幂次是一定有原根的，2的幂次是不一定有原根的。 2.求原根 从小到大或随机枚举\(g\)，然后判断原根。 \(\phi(m) = p1^{e1}p2^{e2}...pk^{ek}\) \(ord = p1^{a1}p2^{a2}...pk^{ak}\) 对于素数\(p\)，只要判断所有的\(m|p-1\)(看它的阶是不是\(\phi(m)\)这里是\(p-1\),说明我们一个因子都不能除掉，因为它的初值就是\(\phi(m)\))然后\(g^{\frac{p-1}{pi}}\neq 1 (\bmod m)\)即可。 记住\(p\)的原根不一定是\(p^2\)的原根。 对于素数幂次，如果\(a\)是\(p\)的原根，存在一个\(a+tp\)是\(p^2\)的原根，并且当\((a+tp)^{p-1}\)模\(p\)不等于1就行。 如果\(a\)是\(p^2\)的原根，那么一定是更高层次的原根。 结论： g是很多的，严格意义上来说有\(\phi(p)-1\)个 最小的原根不会很大 (重要)若\(g\)是一个原根的话，所有\(1\)到\(m\)之间与\(m\)互质的数都会在循环节里面出现，可以表示为\(g^i(0<=i<\phi(m))\) eg.a = 3,m = 7 1 ——>3——>2 ——>6——>4——>5 ↑ | ———————6————————— 例题： 原根 回答T组询问，每次给一个素数p，输出它最小的原根g。 //给定素数p，回答T(1e5)个询问。 //给定一个a，问最小的正数x满足ax≡1(mod p)。 #include using namespace std; typedef long long ll; const int N = 1010; int pf[N]; ll ksm(ll a,ll b,ll mod) { ll ans = 1,base = a; while(b) { if(b&1) { ans = ans*base; ans%=mod; } base = base*base; base%=mod; b>>=1; } return ans; } int main() { int p,T; cin>>T; for(int i = 1;i<=T;i++) { cin>>p; int m = p-1,t = 0; for(int i = 2;i*i<=m;i++) { if(m%i==0) { pf[t++] = i; while(m%i==0)m/=i; } } if(m!=1) pf[t++] = m; for(int g = 1;g { bool ok = true; int d = p-1; for(int i = 0;i { if(ksm(g,d/pf[i],p)==1) { ok = false; break; } } if(ok) { cout< break; } } } return 0; } 三、指数方程 1.理解 指数方程\(a^x ≡ b(\bmod m)\)，其中\((a,m) = 1\) $x = 0 $ ~ $ \phi(m)-1$之间的 2.解法 1.暴力解法,时间复杂度O(m)： for(x = 0...\(\phi(m)\)-1）{ 累乘，看\(a^x \bmod m\)是不是等于\(b\) } 2.正解：令\(T = ceil(\sqrt{m})\) ,对于\(0到m-1\)之间的数一定能表示成\(qT+r\)（商+余数）,其中\(q\in[0,T-1],r\in[0,T-1]\) eg. m = 100,对于0~99之间的数都可以表示成10q+r 那么\(a^x ≡ b(\bmod m)\)就可以写成\(a^{qT+r} ≡ b(\bmod m)\) 未知数由原来的x变为了q和r 现在问题变成了：\((a^T)^q ≡ ba^{-r} (\bmod m )\)其中\(q\in[0,T-1],r\in[0,T-1]\) \(a^{T*0}a^{T*1}a^{T*2}...a^{T*(T-1)}\) \(b*a^{-0}*b*a^{-1}*b*a^{-2}...b*a^{-(T-1)}\) 相当于给你两列数，问你有没有相同的数字，可以用hash或者map写，时间复杂度O(T*log)。 我们写的时候令\(x = q*T-r\)其中\(q\in[1,T],r\in[1,T]\) \((a^{T})^q ≡ b*a^r (\bmod m)\) eg1指数方程1 给定素数p，回答T(1e5)个询问。 给定一个a，问最小的正数x满足ax≡b(mod p)。 #include using namespace std; typedef long long ll; int a,b,m; ll ksm(ll a,ll b,ll mod) { ll ans = 1,base = a; while(b) { if(b&1) { ans = ans*base; ans%=mod; } base = base*base; base%=mod; b>>=1; } return ans; } void solve() { cin>>a>>b>>m; int T = sqrt(m)+2;//小心精度误差，我们+2 ll v = ksm(a,T,m),d = 1; unordered_map for(int q = 1;q<=T;q++) { d = d*v%m; //因为我们要求较小的解，如果我们有两个相同的d，取小的那个 if(!ha.count(d))ha[d] = q*T; } int ans = m+1; d = b; for(int r = 1;r<=T;r++) { d = d*a%m; if(ha.count(d))ans = min(ans,ha[d]-r); } if(ans>=m)cout<<-1< else cout< } int main() { int t; cin>>t; while(t--) { solve(); } return 0; } eg2.[指数方程2](指数方程2 - 题目 - Daimayuan Online Judge) 题意：回答\(T\)组询问，每次给一个数\(a,b,m\)输出最小的非负整数\(x\)满足\(a^x≡b(\bmod m)\)。 思路： 因为不一定互质，就不能和上一题那样写了。为什么呢？ 因为\(a^{qT-r}≡b (\bmod m)和a^{qT} ≡ b*a^r(\bmod m)\)只有在\(a和m\)互质的情况下是可以互推的。 那怎么办呢？如果不互质，我们就除到它互质为止 举个例子： \(6^x ≡ 456(\bmod 600)\) \(6*6^{x-1}≡456(\bmod m)\) \(6^{x - 1}≡76(\bmod 100)\) \(6*6^{x - 2}≡76(\bmod 100)\) \(3*6^{x - 2}≡38(\bmod 50)\) \(6^{x - 2}≡46(\bmod 50)\) \(6*6^{x - 3}≡46(\bmod 50)\) \(3*6^{x - 3}≡23(\bmod 25)\) \(6^{x - 3}≡16(\bmod 25)\) 现在它们互质了，可以用\(BSGS\)写了 最后\(x = 6\)是最小正整数解 总结一下就是： \(a^x ≡ b(\bmod m)\) \(a^{x-t} ≡ b(\bmod m)\) while((a,m)!=1) { if(b==1)x = t; int g = gcd(a,m); if(g%b)无解 else{ a/g*a^{x-t-1}≡b/g(mod m/g) a^{x-t-1} ≡ b/g*(a/g)^{-1}(mod m/g) } } 每次都会除掉一个gcd,这个过程最多会迭代log次 那么写法为： for(x = 0~30)看看有没有解 然后木有的话，直接写成a^30 * a^{x-30} ≡ b（mod m) g = (a^30,m) a^{x-30} ≡ b/g(a^30/g)(mod m/g) 对于\(a^{30}\)怎么办嘞，因为是求和\(m\)的gcd，那我们可以求\(2^{30}\bmod m\),如果mod完之后等于0了，除非b也是0，否则无解 #include using namespace std; typedef long long ll; int a,b,m; ll gcd(ll a,ll b) { if(b==0)return a; else return gcd(b,a%b); } ll ksm(ll a,ll b,ll mod) { ll ans = 1,base = a; while(b) { if(b&1)ans = ans*base%mod; base = base*base%mod; b>>=1; } return ans; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x = 1,y = 0; return a; } ll d = exgcd(b,a%b,y,x); y -= (a/b)*x; return d; } //求a*x = b(mod m)的解 ll modequ(ll a,ll b,ll m) { ll x,y; ll d = exgcd(a,m,x,y); if(b%d)return -1; m/=d,a/=d,b/=d; x = x*b%m; if(x<0)x+=m; return x; } int MAGIC = 30; void solve() { int a,b,m; cin>>a>>b>>m; ll v = 1; for(int i = 0;i { if(v == b) { cout< return; } v = v*a%m; } //v * a^{x-30} = b(mod m); ll g = gcd(v,m); if(b%g) { cout<<-1< return; } b/=g,m/=g; a%=m; //v/g * ? = b/g(mod m) b = modequ(v/g,b,m); //BSGS int T = sqrt(m)+2;//小心精度误差，我们+2 v = ksm(a,T,m); ll d = 1; unordered_map for(int q = 1;q<=T;q++) { d = d*v%m; //因为我们要求较小的解，如果我们有两个相同的d，去小的那个 if(!ha.count(d))ha[d] = q*T; } int ans = m+1; d = b; for(int r = 1;r<=T;r++) { d = d*a%m; if(ha.count(d))ans = min(ans,ha[d]-r); } if(ans>=m)cout<<-1< else cout< } int main() { int t; cin>>t; while(t--) { solve(); } return 0; }