Order and primitive root and exponential equations(阶、原根和指数方程)
一、概念
1、阶
阶：上面的x就是阶
2、原根
的阶为的数
3、指数方程(BSGS)
BSGS(baby step giant step)
不暴力的解
二、阶
1.理解
如果，那么记为最小的正整数使得
，反证法。
阶可以理解为循环长度的是多少。
我们不停的乘a模，看看循环长度是多少，我们绕着循环走，走步一定会走回原来的地方。最小的正整数使得,称为的阶。
eg.a = 2,m = 7
1 ——>2——>4
↑ |
———3———
eg2.a = 3,m = 7
1 ——>3——>2 ——>6——>4——>5
↑ |
———————6—————————
2.求阶
那么我们怎么去求这个阶呢？
1.(纯暴力)因为我们知道步只会一定会循环，那我们从1 for 到看看最小的是多少。
2.阶|，我们枚举的所有因子去找到最小的
3.(正解)我们求阶的时候可以从开始依次除掉每个因子判断。
for(每个因子pi){
while(%&&% ){
d/=pi
}
}
最后的这个d就是答案
eg. a = 9,m = 31,
一开始，令
对于因子，d有2这个因子，再看d能不能把2这个因子除掉，那，去看是不是等于1的，是的话就把d除掉2这个因子，d = 15，接着看3这个因子，我们发现所以这个因子不能被除掉。因为我们始终要保证
,d = 15
不行
不行
所以这里a mod m的阶是15。
从
比如上述例子：
例题：
阶
给定素数p，回答T(1e5)个询问。
给定一个a，问最小的正数x满足ax≡1(mod p)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
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<t;i++)
while(d%pf[i]==0&&ksm(a,d/pf[i],p)==1)
d/=pf[i];
cout<<d<<endl;
}
return 0;
}
|
三、原根(useful)
1.理解
如果的阶为,那么为的原根。
阶是在互质数 (a,m)间的定义：满足 的最小 n 被称作 a 模 m 的阶
明显，在 a,m 不互质时，a 的无论多少次幂全都是 的倍数，故不可能取到 1；
而当互质时，依据扩展欧拉定理，必有 ，但也不排除存在更小的 。它未必是最小的，所以不一定是阶，而当的阶时，我们称a为m的一个原根。
构成了模的简化剩余系。
只有存在原根(这里的的奇素数)
结论(记一下):奇素数的幂次是一定有原根的，2的幂次是不一定有原根的。
2.求原根
从小到大或随机枚举，然后判断原根。
对于素数，只要判断所有的(看它的阶是不是这里是,说明我们一个因子都不能除掉，因为它的初值就是)然后即可。
记住的原根不一定是的原根。
对于素数幂次，如果是的原根，存在一个是的原根，并且当模不等于1就行。
如果是的原根，那么一定是更高层次的原根。
结论：
- g是很多的，严格意义上来说有个
- 最小的原根不会很大
- (重要)若是一个原根的话，所有到之间与互质的数都会在循环节里面出现，可以表示为
eg.a = 3,m = 7
1 ——>3——>2 ——>6——>4——>5
↑ |
———————6—————————
例题：
原根
回答T组询问，每次给一个素数p，输出它最小的原根g。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include<bits/stdc++.h>
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<p;g++)
{
bool ok = true;
int d = p-1;
for(int i = 0;i<t;i++)
{
if(ksm(g,d/pf[i],p)==1)
{
ok = false;
break;
}
}
if(ok)
{
cout<<g<<endl;
break;
}
}
}
return 0;
}
|
三、指数方程
1.理解
指数方程，其中
~ 之间的
2.解法
1.暴力解法,时间复杂度O(m)：
for(x = 0…-1）{
累乘，看是不是等于
}
2.正解：令 ,对于之间的数一定能表示成（商+余数）,其中
eg. m = 100,对于0~99之间的数都可以表示成10q+r
那么就可以写成
未知数由原来的x变为了q和r
现在问题变成了：其中
$a^{T0}a^{T1}a^{T2}…a^{T(T-1)}$
$ba^{-0}ba^{-1}ba^{-2}…ba^{-(T-1)}$
相当于给你两列数，问你有没有相同的数字，可以用hash或者map写，时间复杂度O(T*log)。
我们写的时候令其中
给定素数p，回答T(1e5)个询问。
给定一个a，问最小的正数x满足ax≡b(mod p)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<bits/stdc++.h>
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;
ll v = ksm(a,T,m),d = 1;
unordered_map<int,int>ha;
for(int q = 1;q<=T;q++)
{
d = d*v%m;
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<<endl;
else cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
|
题意：回答组询问，每次给一个数输出最小的非负整数满足。
思路：
因为不一定互质，就不能和上一题那样写了。为什么呢？
因为只有在互质的情况下是可以互推的。
那怎么办呢？如果不互质，我们就除到它互质为止
举个例子：
现在它们互质了，可以用写了
最后是最小正整数解
总结一下就是：
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)
对于怎么办嘞，因为是求和的gcd，那我们可以求,如果mod完之后等于0了，除非b也是0，否则无解
