最新消息:热烈庆祝IT小记上线!

bzoj-3239 Discrete Logging

题意:

给出方程A^x=B (mod C),C是质数;

求x的最小非负整数解,无解输出-1;


题解:
这是一道BSGS的模板题;

BSGS的实现方法其实很像分块,或者说是一种折半搜索的思想;

根据欧拉定理,A^x的值会在[0,φ(C))中循环,也就是解不会大于C;

首先将C分成√C块,求出A^0,A^1,...A^(√C-1)的值;

注意:这里以及之后的√C都是C的算术平方根,并且上取整;

这一步工作相当于搜索的前一半,或者说是分块的预处理;

我们将其插入哈希表中;

接下来令D=A^(√C),那么我们再枚举D^0,D^1,...D^(√C-1);

将枚举的这东西扔到右面A^x'=B*inv(D^i) (mod C)

inv(x)指x对于C的逆元;

那就这已经是一个子问题了!

直接到哈希表中去查找B*inv(D^i)%C,查到对应的指数就是x';

而原方程的解就是i*√C+x'了,且恰好最小;

分析一下复杂度,两次枚举都是O(√C)的;

哈希表的复杂度期望O(1),B*inv(D^i)每次累乘D的逆元也是O(1);

总复杂度O(√C),似乎也蛮优越的;


问题来了,哈希表这么写?

直接数组会冲突,map会用蜜汁复杂度卡死你;

只好挂链表了,但是有一种似乎十分优越的写法如下:

struct Hash_Set
{
	ll head[N], X[N], val[N], next[N], tot;
	void clear()
	{
		tot = 0;
		memset(head, 0, sizeof(head));
		memset(next, 0, sizeof(next));
		memset(val, -1, sizeof(val));
		memset(X, 0, sizeof(X));
	}
	ll& operator [] (ll x)
	{
		ll index = x%N;
		for (ll i = head[index]; i; i = next[i])
			if (X[i] == x)
				return val[i];
		next[++tot] = head[index];
		head[index] = tot;
		X[tot] = x;
		return val[tot];
	}
}hash;

我只是又一次体会到C++语法的博大精深而被吓死了而已;

返回地址。。重载[]符号。。。;

这样代码就可以变的好简洁好简洁啦!

尤其是后面的题比较乱,把BSGS函数化是很重要的吧;


代码:


#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 140142
using namespace std;
typedef long long ll;
struct Hash_Set
{
	ll head[N], X[N], val[N], next[N], tot;
	void clear()
	{
		tot = 0;
		memset(head, 0, sizeof(head));
		memset(next, 0, sizeof(next));
		memset(val, -1, sizeof(val));
		memset(X, 0, sizeof(X));
	}
	ll& operator [] (ll x)
	{
		ll index = x%N;
		for (ll i = head[index]; i; i = next[i])
			if (X[i] == x)
				return val[i];
		next[++tot] = head[index];
		head[index] = tot;
		X[tot] = x;
		return val[tot];
	}
}hash;
ll inv(ll x, ll mod)
{
	ll ret = 1, y = mod - 2;
	while (y)
	{
		if (y & 1)
			ret = (ret*x) % mod;
		x = (x*x) % mod;
		y >>= 1;
	}
	return ret;
}
ll BSGS(ll A, ll B, ll C)
{
	hash.clear();
	ll bk = ceil(sqrt(C)), i, j, k, D, temp;
	for (i = 0, D = 1; i < bk; i++, D = (D*A) % C)
	{
		if (hash[D] == -1)
			hash[D] = i;
	}
	temp = inv(D, C);
	for (i = 0, k = B; i <= bk; i++, k = (k*temp) % C)
	{
		if ((j = hash[k]) != -1)
			return i*bk + j;
	}
	return -1;
}
int main()
{
	ll A, B, C, ans;
	while (scanf("%lld%lld%lld", &C, &A, &B) != EOF)
	{
		ans = BSGS(A, B, C);
		if (ans == -1)
			puts("no solution");
		else
			printf("%lld\n", ans);
	}
	return 0;
}



猜您喜欢

备案号:苏ICP备12016861号-4