Reincarnation

正因为梦易碎，才格外美好。

Baby Step, Giant Step算法

发表于 更新于 分类于 ，
本文字数： 24k 阅读时长 ≈ 22 分钟

“大步小步，永不服输。”

Baby Step, Giant Step

用于求解 的 的问题。

求解

根据欧拉定理我们得知 ，推理得知：

那么我们缩小求值范围得到 。

但 的范围也已经够大了，所以我们对这一段值域进行分块处理。

我们设 ，而 ，这样可以不重不漏遍历完 的所有取值，所以需要特判 。

考虑优化方程：

把 写成 是为了提到式子右边避免处理逆元。

容易发现， 至多有 个取值，相对应的， 也只有 个取值。我们现在需要其对应关系 。

考虑对 建立一个哈希表，然后枚举 看在 的情况下是否存在一个 与之对应，如果有，则有解。

时间复杂度为 ，其中一支 是 std::map 的时间，另一支 是快速幂的时间。

题目简介

题目名称：可爱的质数 /

题目来源：天津省选

评测链接 ：https://www.luogu.com.cn/problem/P3846
评测链接 ：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1166

形式化题意：给定 ，其中 是质数，求最小的非负整数 使得 ，如果无解输出 no solution 。

数据范围：

即板子。

参考实现
 
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
std::map<ll,ll>Hash;
ll a,b,Mod;
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
inline ll BSGS(ll a,ll b)
{
	Hash.clear();
	if(b%Mod==1) return 0;
	ll ans=INF;
	ll k=std::sqrt(Mod)+1;
	for(ll y=0;y<k;++y) Hash[1ll*b*qPow(a,y)%Mod]=y;
	for(ll t=1;t<=k;++t)
	{
		ll lef=qPow(a,k*t);
		if(Hash[lef]) checkMin(ans,(1ll*k*t-Hash[lef]+(Mod-1))%(Mod-1));
	}
	return ans==INF?-1:ans;
}

这个实现好像总感觉哪里有问题，欢迎求 ，但大概就是这样一个实现法。

Ex Baby Step, Giant Step

与不同 唯一不同的点在于，并不限制 是否为质数，也就是 不一定互质。

求解

我们可以分类讨论来解决问题。

  • 若 ，则

  • 设 ，再次对 分类讨论。

    • 若 ，直接执行 算法。
    • 若 ，则转换为 。

我们现在只考虑 的情况。

如果 ，则无解，这是显然的。

那考虑继续转换问题：

这样的话，我们把原来的同余方程，转换成了另一个同余方程，可以证明，至多转换 次之后， 互质，这个时候就可以使用 的问题了。

题目简介

题目名称：扩展 /

题目来源：

评测链接 ：https://www.luogu.com.cn/problem/P4195
评测链接 ：https://www.spoj.com/problems/MOD

形式化题意：求满足 的最小的非负整数 。

数据范围：

有递归写法，也可以使用 while 来进行，注意求逆元在不保证 为质数的时候，应当是 ，或者使用 来求逆元。然后就是卡常的问题，对于一些幂，可以舍去快速幂，用递推方式得到。而哈希表也选择快一点的哈希表或者手写比较合适，否则会多套几支 。

参考实现
 
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
int exgcd(int a,int b,int &x,int &y)
{
	if(!b){ x=1,y=0;return a; }
	int gcd=exgcd(b,a%b,y,x);
	y-=a/b*x;return gcd;
}
inline int qPow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%p;
		a=1ll*a*a%p;b>>=1;
	}
	return res;
}
inline int Bsgs(int a,int b,int p)
{
	if(1%p==b%p) return 0;
	if(a%p==0) return b==0?1:-INF;
	// std::unordered_map<int,int>Hash;
	Hash.clear();
	int ans=INF;
	int k=std::sqrt(p)+1;
	for(int y=0;y<k;++y) Hash[1ll*b*qPow(a,y,p)%p]=y;
	int ak=qPow(a,k,p);
	for(int t=1,at=ak;t<=k;++t,at=1ll*at*ak%p) if(Hash.find(at)!=Hash.end()) checkMin(ans,k*t-Hash[at]);
	return ans==INF?-INF:ans;
}
inline int exBsgs(int a,int b,int p)
{
	b=(b%p+p)%p;
	if(1%p==b%p) return 0;
	int x,y,gcd=exgcd(a,p,x,y);
	if(gcd>1)
	{
		if(b%gcd) return -INF;
		exgcd(a/gcd,p/gcd,x,y);
		return exBsgs(a,1ll*b/gcd*x%(p/gcd),p/gcd)+1;
	}
	return Bsgs(a,b,p);
}

例题

随机数生成器

题目简介

题目名称：随机数生成器
题目来源：山东

评测链接：https://www.luogu.com.cn/problem/P3306

形式化题意：有一个序列 ，给定 ，该序列的生成结构满足 ，求 使得 ，或输出无解。多测。

数据范围： ， 为质数。

化简递推式： 。

当然， 的时候上述公式并没有意义，所以在 的时候特判。

所以我们就求解 即可。

化简式子得到 ，然后用 求解得到 的值，得到答案。

期间有很多可以特判的地方，需要注意。

AC Code
 
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// ----- Eternally question-----
// Problem: P3306 [SDOI2013] 随机数生成器
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3306
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-06 16:28:09
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class Test>
inline void read(Test &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class Test,class ...T1>
inline void read(Test &x,T1 &...x1){ read(x),read(x1...); }
template<class Test>
inline void write(Test x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class Test,class ...T1>
inline void write(Test x,T1 ...x1){ write(x),write(x1...); }
template<class Test>
inline bool checkMax(Test &x,Test y){ return x<y?x=y,1:0; }
template<class Test>
inline bool checkMin(Test &x,Test y){ return x>y?x=y,1:0; }
int Test;
ll a,b,x1,t,p;
ll qPow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%p;
		a=a*a%p;b>>=1;
	}
	return ans;
}
ll inv(ll x){ return qPow(x,p-2); }
std::unordered_map<ll,int> Hash;
ll Bsgs(ll a,ll b)
{
	int m=std::ceil(std::sqrt(p));
	Hash.clear();
	for(int i=0;i<=m;i++) Hash[b]=i,b=b*a%p;
	a=qPow(a,m);b=a;
	for(int i=1;i<=m;i++)
	{
		if(Hash.count(b)) return i*m-Hash[b];
		b=b*a%p;	 
	}
	return -2;
}
int main()
{
	read(Test);
	while(Test--)
	{
		read(p,a,b,x1,t);
		if(a==1)
		{
			t=(t-x1+p)%p;
			if(b==0){ puts(t?"-1":"1");continue; }
			write(t*inv(b)%p+1,'\n');
			continue;
		}
		if(a==0)
		{
			if(t==b) puts("2");
			else if(t==x1) puts("1");
			else puts("-1");
			continue;
		}
		t=(t*(a-1)%p+b)%p;
		if((a*x1%p-x1+b+p)%p==0){ puts(t?"-1":"1");continue; }
		write(Bsgs(a,t*inv((a*x1%p-x1+b+p)%p)%p)+1,'\n');
	}
}
/*

*/

计算器

题目简介

题目名称：计算器
题目来源：山东 / 一本通 例

评测链接 ：https://www.luogu.com.cn/problem/P2485

评测链接 ：https://loj.ac/p/10214

给定 有三种操作：

  1. 给定 求 ；
  2. 给定 求满足 的最小非负整数 ；
  3. 给定 求满足 的最小非负整数 。

多测，无解输出 Orz, I cannot find x! 。

数据范围： ， 为质数。

第一个操作快速幂解决，第二个操作我们化简 ，用逆元解决（费马小定理或者扩欧都可以解决），第三个操作就是 的板子。注意判断无解的情况。

AC Code
 
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// ----- Eternally question-----
// Problem: P2485 [SDOI2011]计算器
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2485
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-06 15:47:55
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int INF=0x3f3f3f3f;
int Test,K,a,b,p;
inline int qPow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%p;
		a=1ll*a*a%p;b>>=1;
	}
	return res;
}
inline int Bsgs(int a,int b,int p)
{
	if(a%p==0) return b%p==0?1:-INF;
	if(b%p==1%p) return 0;
	std::unordered_map<int,int>Hash;
	int k=std::sqrt(p)+1;Hash.clear();
	for(int y=0,ay=1;y<k;++y,ay=1ll*ay*a%p) Hash[1ll*b*ay%p]=y;
	int ak=qPow(a,k,p),ans=INF;
	for(int t=1,tk=ak;t<=k;++t,tk=1ll*tk*ak%p)
	{
		if(Hash.find(tk)==Hash.end()) continue;
		int res=1ll*k*t-Hash[tk];
		checkMin(ans,res);
	}
	return ans==INF?-INF:ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test,K);
	while(Test--)
	{
		read(a,b,p);
		if(K==1) write(qPow(a,b,p),'\n');
		else if(K==2)
		{
			if(b%p==0) puts("0");
			else if(a%p==0) puts("Orz, I cannot find x!");
			else write(1ll*qPow(a,p-2,p)*b%p,'\n');
		}
		else
		{
			int ans=Bsgs(a,b,p);
			if(ans==-INF) puts("Orz, I cannot find x!");
			else write(ans,'\n');
		}
	}
	return 0;
}
/*

*/

签到题 / 多少个 1？

题目简介

题目名称：签到题 / 多少个

题目来源：洛谷月赛
评测链接：https://www.luogu.com.cn/problem/P4884

形式化题意：求出最小的正整数 使得 ，保证有解。

数据范围： ，其中 为质数。

简单来讲，就是求 ，我们根据同余方程的性质，将左右两边同时乘以 ，变为 ，然后再加上一个 ，得到 ，此时的左边可以化简得到 ，我们设 ，化简为 ，那显而易见了。

由于 ，乘法会溢出 long long ，所以可以选择龟速乘或者 __int128_t 代替，但是龟速乘会多一个 ，好像会时间 ，注意的是 std::unordered_map 并不支持 __int128_t 。

AC Code
 
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// ----- Eternally question-----
// Problem: P4884 多少个 1？
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4884
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-01-07 14:45:48
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using int128=__int128_t;
const int128 INF=0x3f3f3f3f3f3f3f3f;
int128 a,b,p;
inline int128 qPow(int128 a,int128 b)
{
	int128 res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;b>>=1;
	}
	return res;
}
inline int128 inv(int128 x){ return qPow(x,p-2); }
inline int128 Bsgs(int128 a,int128 b,int128 p)
{
	if(b%p==1) return 0;
	int128 k=(int128)std::sqrt((double)p)+1;
	std::map<int128,int>Hash;
	Hash.clear();
	int128 ay=1,ak=qPow(a,k),ans=INF;
	for(int y=0;y<k;++y,ay=ay*a%p) Hash[b*ay%p]=y;
	int128 tk=ak;
	for(int x=1;x<=k;++x,tk=tk*ak%p)
	{
		if(Hash.find(tk)==Hash.end()) continue;
		int128 res=k*x-Hash[tk];
		if(res>=0) checkMin(ans,res);
	}
	return ans==INF?-INF:ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(b,p);a=10,b=(b*9+1)%p;
	write(Bsgs(a,b,p));
	return 0;
}
/*

*/

New Product

题目简介

题目名称：

题目来源：洛谷原创
评测链接：https://www.luogu.com.cn/problem/P4028

形式化题意：有一个数 初始为 ，每一秒会执行 （按顺序执行），求最短时间使得 。若无解，输出 Couldn't Produce!。给定 ，多测。

数据范围：， 为质数。

简化一下题意，得到当 秒时， 应当为 ，那问题就在于求出一个最小的 使得：

这就是个 的板子，注意判断 的情况。

AC Code
 
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
const int INF=0x3f3f3f3f;
int Test;
ll a,b,p;
inline ll qPow(ll a,ll b,ll p)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;b>>=1;
	}
	return res;
}
inline int Bsgs(int a,int b,int p)
{
	if(a%p==0) return b==0?1:-INF;
	if(b%p==1%p) return 0;
	std::unordered_map<int,int>Hash;
	int k=std::sqrt(p)+1;Hash.clear();
	for(int y=0,ay=1;y<k;++y,ay=1ll*ay*a%p) Hash[1ll*b*ay%p]=y;
	int ak=qPow(a,k,p),ans=INF;
	for(int t=1,tk=ak;t<=k;++t,tk=1ll*tk*ak%p)
	{
		if(Hash.find(tk)==Hash.end()) continue;
		int res=1ll*k*t-Hash[tk];
		checkMin(ans,res);
	}
	return ans==INF?-INF:ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(p,a,b);
		a%=p;
		// if(b>=p){ puts("Couldn't Produce!");continue; }
		ll res=Bsgs(a,b,p);
		if(res==-INF) puts("Couldn't Produce!");
		else write(res,'\n');
	}
	return 0;
}
/*

*/

CQOI2018 破解D-H协议

题目简介

题目名称：破解 协议

题目来源：重庆 省选第一天第一题

评测链接 ：https://www.luogu.com.cn/problem/P4454
评测链接 ：https://loj.ac/p/2531

给定一个质数 以及其一个原根 ，每次给定两个整数 ，满足：

求 。多测。as

数据范围：。

时空限制：

原题意很复杂（没有 就很难受），大概理解一下，我们可以推出：

已知了 ，就可以一次 ，一次快速幂解决了。

但事实上，只有 ，这样实现已经是我们的最优秀的实现方法 了。

当前实现
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline int Bsgs(int a,int b)
{
	if(a%P==0) return b==0?1:-INF;
	if(b%P==1) return 0;
	std::unordered_map<int,int>Hash;
	int k=std::sqrt(P)+1;
	int ay=1;
	for(int y=0;y<k;++y,ay=(ll)ay*a%P) Hash[(ll)b*ay%P]=y;
	int ans=INF,ak=qPow(a,k),at=qPow(a,k);
	for(int t=1;t<=k;++t,ak=(ll)ak*at%P)
	{
		if(Hash.find(ak)==Hash.end()) continue;
		int res=k*t-Hash[ak];
		if(res>0) checkMin(ans,res);
	}
	return ans==INF?-INF:ans;
}

但是否这道题有其特殊的性质呢。

注意到质数与原根对于每一个测试点是固定的，而我们每一次的询问都要调用 ，而其中我们的哈希表记录的是所有的 。那我们考虑改变一下得到的式子：

因为有 ，所以可以预处理右半部分，以避免每一次询问 的预处理复杂度。然后对于所有的类似于 都给它预处理出来，优化常数，在最后使用欧拉定理稍微优化一下快速幂的常数令 ，然后就可以次优解通过本题了。

对于这种多次询问且 相等的 ，可以优化到 的复杂度，将预处理提出，然后取块长为 ，就可以得到这样的时间复杂度（但由于众所周知的常数原因也没快多少甚至还慢了些，甚至还爆了 long long 然后翻车）。

AC Code
 
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// ----- Eternally question-----
// Problem: P4454 [CQOI2018]破解D-H协议
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4454
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-15 16:15:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int INF=0x7f7f7f7f;
int G,P,Test,A,B,sP,aK;
inline int qPow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
inline int inv(int x){ return qPow(x,P-2); }
std::unordered_map<int,int>Hash;
inline int Bsgs(int b)
{
	if(b%P==1) return 0;
	int iv=inv(b),ans=INF;
	for(int t=1,ak=aK;t<=sP;++t,ak=(ll)ak*aK%P)
	{
		if(Hash.find((ll)ak*iv%P)==Hash.end()) continue;
		int res=(ll)sP*t-Hash[(ll)ak*iv%P];
		if(res>=0) return res;
	}
	return -INF;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(G,P,Test);
	sP=std::sqrt(P)+1;aK=qPow(G,sP);
	for(int y=0,ay=1;y<sP;++y,ay=(ll)ay*G%P) Hash[ay]=y;
	while(Test--)
	{
		read(A,B);
		write(qPow(B,Bsgs(A)),'\n');
	}
	return 0;
}
/*

*/

快乐肥宅

题目简介

题目名称：【】快乐肥宅

题目来源：洛谷原创
评测链接：https://www.luogu.com.cn/problem/P5345

形式化题意：给定 组 ，第 秒会有 ，问最小时间使得 。

数据范围：

我们可以得到 个高次同余方程形如 ，从而解出 个不同的 ，不难发现， 会在一定数量后进入一个直观的循环，从而得到 个同余方程形如：（ ），这样就可以用 来进行合并，但由于 并没有被限制为质数，所以需要使用 。

AC Code
 
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// ----- Eternally question-----
// Problem: P5345 【XR-1】快乐肥宅
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5345
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-15 19:15:32
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
const int MAXN=1e3+10,MAXS=1e7+10;
const int INF=0x3f3f3f3f;
const int INFTY=1e9;
int N,K[MAXN],R[MAXN],G[MAXN];
int T[MAXN],D[MAXN];
int exgcd(int a,int b,int &x,int &y)
{
	if(!b){ x=1,y=0;return a; }
	int gcd=exgcd(b,a%b,y,x);
	y-=a/b*x;return gcd;
}
inline int inv(int a,int p)
{
	int x,y;
	exgcd(a,p,x,y);
	return (x%p+p)%p;
}
inline int qPow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%p;
		a=1ll*a*a%p;b>>=1;
	}
	return res;
}
inline ll qMul(ll a,ll b,ll p)
{
    ll res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=(a+a)%p;b>>=1;
    }
    return res;
}
inline int Bsgs(int a,int b,int p)
{
	std::unordered_map<int,int>Hash;
	int k=std::sqrt(p)+1;
	int ay=1;
	for(int y=0;y<k;++y,ay=(ll)ay*a%p) Hash[(ll)b*ay%p]=y;
	int ak=qPow(a,k,p),at=qPow(a,k,p);
	for(int t=1;t<=k;++t,ak=(ll)ak*at%p)
	{
		if(Hash.find(ak)==Hash.end()) continue;
		int res=k*t-Hash[ak];
		if(res>=0) return res;
	}
	return -1;
}
inline Pir exBsgs(int a,int b,int p)
{
	if(p==1) return (Pir){0,1};
	a%=p,b%=p;
	int x,y;
	int g=exgcd(a,p,x,y),f=1,k=0;
	while(g>1)
	{
		if(b%g)
		{
			if(b==1) return (Pir){0,-1};
			return (Pir){-1,-1};
		}
		++k,b/=g,p/=g;
		f=(ll)f*(a/g)%p;
		g=exgcd(a,p,x,y);
		if(f==b)
		{
			if(g>1) return {k,-1};
			int y=Bsgs(a,1,p);
			return (Pir){k,y};
		}
	}
	x=Bsgs(a,(ll)b*inv(f,p)%p,p);
	if(x==-1) return (Pir){-1,-1};
	y=Bsgs(a,1,p);
	return (Pir){x%y+k,y};
}
ll A,B;
inline int merge(ll a,ll b)
{
	int x,y;
	ll gcd=exgcd(A,a,x,y),c=B-b;
	if(c%gcd) return -1;
	c/=gcd;
	x=(x*c%a+a)%a;
	ll lcm=A/gcd*a;
	B=(B-A*x%lcm+lcm)%lcm;
	A=lcm;
	return 1;
}
inline int div_ceil(int a,int b)
{ return (a-1)/b+1;}
int Excrt(int n,int x)
{
	A=D[1],B=T[1];
	for(int i=2;i<=n;++i)
	{
		if(A>INFTY&&(B-T[i])%D[i]) return -1;
		else if (A<=INFTY&&merge(D[i],T[i])==-1) return -1;
	}
	if(B<x) B+=div_ceil(x-B,A)*A;
	if(B>INFTY) return -1;
	return B;
}
int Mx,pos=-1;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(K[i],G[i],R[i]);
	for(int i=1;i<=N;++i)
	{
		auto res=exBsgs(K[i],R[i],G[i]);
		T[i]=res.first,D[i]=res.second;
	}
	for(int i=1;i<=N;++i) if(T[i]==-1) return puts("Impossible"),0;
	for(int i=1;i<=N;++i)
	{
		if(D[i]==-1)
		{ pos=T[i];continue; }
		checkMax(Mx,T[i]);
	}
	if(pos!=-1)
	{
		for(int i=1;i<=N;++i)
			if((D[i]==-1&&pos!=T[i])||(D[i]!=-1&&(pos<T[i]||(pos-T[i])%D[i])))
			{ puts("Impossible");return 0;}
		write(pos);
		return 0;
	}
	int ans=Excrt(N,Mx);
	if(ans==-1) puts("Impossible");
	else write(ans);
	return 0;
}
/*

*/

正统板子

上述很多题都是边学边写的，有些是自己糊的有些是贺的题解，然后导致出现了各种各样不一样的常数不同的板子，所以这里给出我最后使用的板子，以供背诵（常数较小的一种）。

BSGS
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline int Bsgs(int a,int b)
{
	if(a%P==0) return b==0?1:-INF;
	if(b%P==1) return 0;
	std::unordered_map<int,int>Hash;
	int k=std::sqrt(P)+1;
	int ay=1;
	for(int y=0;y<k;++y,ay=(ll)ay*a%P) Hash[(ll)b*ay%P]=y;
	int ans=INF,ak=qPow(a,k),at=qPow(a,k);
	for(int t=1;t<=k;++t,ak=(ll)ak*at%P)
	{
		if(Hash.find(ak)==Hash.end()) continue;
		int res=k*t-Hash[ak];
		if(res>=0) return res;
	}
	return -INF;
}
EXBSGS
 
1
2
3
4
5
6
7
8
9
10
11
12
13
inline int exBsgs(int a,int b,int p)
{
	b=(b%p+p)%p;
	if(1%p==b%p) return 0;
	int x,y,gcd=exgcd(a,p,x,y);
	if(gcd>1)
	{
		if(b%gcd) return -INF;
		exgcd(a/gcd,p/gcd,x,y);
		return exBsgs(a,1ll*b/gcd*x%(p/gcd),p/gcd)+1;
	}
	return Bsgs(a,b,p);
}
相关文章