【学习笔记】数论相关

发表于

退役了就学学数论吧
退役后的第一场cf（话说已经半年没打cf了
536f(1106)题是矩乘+bsgs

发现我什么都不会
先贴一些基础的模块吧

求原根：
一个数m有原根的充要条件是m=1,2,4,p^e,2p^e, 其中p为奇素数， e为正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
IL int primitive_rt(int p)//p是奇素数 
{
	int phi=p-1;//p不是素数就改成求phi
	vector<int> fact;
	for(int i=2;i*i<=phi;++i){
		if(phi%i==0){
			fact.pb(i);
			while(p%i==0)	phi/=i;	
		}
	}
	if(phi>1)	fact.pb(phi);
	phi=p-1;
	for(int i=2;i<p;++i){
		bool ok=1;
		for(int j=0;j<fact.size();++j){
			if(ksm(i,phi/fact[j],p)==1){
				ok=0;break;	
			}
		}
		if(ok)	return i;
	}
	return -1;
}

求（一个）离散对数：
//求所有的把map改成map即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
IL int bsgs(int a,int b,int p)//calc x which a^x=b(mod p), (a,p)=1
{
	unordered_map<int,int> ma;
	ma.clear();
	int t=round(sqrt(p))+1;
	//多求一些x不影响答案 
	int tmp=b;
	for(int i=0;i<=t;++i){
		ma[tmp]=i;
		tmp=LL(tmp)*a%p;
	}
	int c=ksm(a,t,p);
	tmp=1;
	for(int i=0;i<=t;++i){
		int j=ma.find(tmp)==ma.end()?-1:ma[tmp];
		if(j>=0&&i*t-j>=0){
			return i*t-j;	
		}
		tmp=LL(tmp)*c%p;	
	}
	return -1;
}

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
IL int exbsgs(int a,int b,int p)//a和p不一定互质
{
	a%=p;b%=p;
	if(b==1)	return 0;
	int v=1,d,cnt=0;
	while((d=gcd(a,p))>1){
		if(b%d)	return -1;
		b/=d;p/=d;++cnt;
		v=LL(v)*a/d%p;
		if(v==b)	return cnt;	//去掉也是对的 
	}
	unordered_map<int,int> ma;
	ma.clear();
	int t=round(sqrt(p))+1;
	//多求一些x不影响答案 
	int tmp=b;
	for(int i=0;i<=t;++i){
		ma[tmp]=i;
		tmp=LL(tmp)*a%p;
	}
	int c=ksm(a,t,p);
	tmp=v;
	for(int i=0;i<=t;++i){
		int j=ma.find(tmp)==ma.end()?-1:ma[tmp];
		if(j>=0&&i*t-j>=0){
			return i*t-j+cnt;	
		}
		tmp=LL(tmp)*c%p;	
	}
	return -1;
}

求（所有）离散底数：

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
int ans[100008],ta;
IL void solve(int a,int b,int p)//calc all x which x^a=b(mod p)
{
	int g=primitive_rt(p);
	a=ksm(g,a,p); 
	unordered_map<int,vector<int> > ma;
	ma.clear();
	int t=round(sqrt(p))/2+1;//调块大小过 
	int tmp=b;
	for(int i=0;i<=t;++i){
		ma[tmp].pb(i);
		tmp=LL(tmp)*a%p;
	}
	int c=ksm(a,t,p);
	tmp=1;
	ta=0;
	int up=p/t+1;//调过块大小要改up 
	for(int i=0;i<=up;++i){
		if(ma.find(tmp)!=ma.end()){
			vector<int> v=ma[tmp];
			for(int j=0;j<v.size();++j){
				int x=i*t-v[j];
				if(x>=0&&x<p-1){
					ans[++ta]=x;	
				}
			}
		}
		tmp=LL(tmp)*c%p;	
	}
	if(ta==0){
		puts("No Solution");	
		return;
	}
	for(int i=1;i<=ta;++i){
		ans[i]=ksm(g,ans[i],p);	
	}
	sort(ans+1,ans+ta+1);
	ta=unique(ans+1,ans+ta+1)-ans-1;
	for(int i=1;i<=ta;++i){
		printf("%d ",ans[i]);	
	}
	putchar('\n');
}