网站建设_app开发,wordpress 微博同步,文山专业网站建设联系电话,什么是品牌网站题意#xff1a;
给定x,n,m,求x^yn(mod m)的解(其中m是素数) 求解一个最小的x满足给定的方程Bx N (mod P) 使用baby_step_giant_step算法。也就是先小步后大步算法。 1、令xi*mj (mceil(sqrt(p)))#xff0c; 那么原式化为 B^(i*m)*B^jN(MOD P) B^jN*B^(-i*m)(MOD P)-----…题意
给定x,n,m,求x^yn(mod m)的解(其中m是素数) 求解一个最小的x满足给定的方程Bx N (mod P) 使用baby_step_giant_step算法。也就是先小步后大步算法。 1、令xi*mj (mceil(sqrt(p))) 那么原式化为 B^(i*m)*B^jN(MOD P) B^jN*B^(-i*m)(MOD P)----------B^jN*B^m^(-i)(MOD P) 2、先预处理B^0,B^1,B^2……B^(m-1),存入HASH表,我使用结构体排序然后二分查找这一步就是baby_step,每次移动1 3、然后快速幂求出B^-m,枚举i如果存在N*B^(-i*m)存在于HASH表中说明存在解xi*mj这一步为giant_step,每次移动m 注意以上解法是最基本的只能对于gcd(B,P)1算法的时间复杂度是O(sqrt(P)*log(sqrt(P))) 模板:此模板m不一定非为质数 #includecstdio
#includealgorithm
#includecstring
#includecmath
#define ll long long
using namespace std;ll b,n,p;
/***************************************/下面就是BSGS的函数集包括所需变量
const int N100009;
const int mod76543;
ll hs[N],id[N],head[N],next[N],tot;
void insert(ll x,ll y)
{int kx%mod;hs[tot]x;id[tot]y;next[tot]head[k];head[k]tot;
}
ll find(ll x)
{int kx%mod;for (int ihead[k];i;inext[i])if (hs[i]x) return id[i];return -1;
}
ll BSGS(ll a,ll b,ll n)
{if (b1) return 0;memset(head,0,sizeof(head));tot0;ll j,msqrt(n*1.0),x1,p1;for (int i0;im;i,pp*a%n) insert(p*b%n,i);for (ll im;in;im)if ((jfind(xx*p%n))!-1) return i-j;return -1;
}
/**************************************/
int main()
{while(scanf(%lld%lld%lld,p,b,n)!EOF)//poj提交一定要有“EOF” {ll ansBSGS(b,n,p);if (ans-1) printf(no solution\n);else printf(%lld\n,ans);} return 0;
}
