首页 > 代码库 > POJ2417 Baby-Step-Gaint-Step 算法
POJ2417 Baby-Step-Gaint-Step 算法
考虑一个问题:A^x%p=B,给定A,B,p,求x的最小非负整数解。
在p是质数的情况下,这个问题比较简单。
A^x=B(mod P) (P is a Prime, A,B<P) Let m = floor(sqrt(P)) Put A^0,A^1,...A^(m-1) into HashSet(You Can Also Use Map in STL),for Example M[A^i]=i.
if A^i=A^j(i<j), M[A^i=A^j]=i.
Enumerate i, Let x=i*m+j, A^(i*m)*A^j=B(mod C) Let E=A^(i*m),F=A^j,E*F=B(mod P) because (E,C)=1,(E,C)|B,we can use EXTgcd to get F.
If F is in the HashSet,then the minimum answer x=i*m+M[F].
Because P is a Prime, and A,B<P, then A^(P-1)=1(mod P). Then if a answer exists, the minimum answer must less then P.
So the range of i is [0,P/m].
If for all i we cannot find a answer, then no solution.
我亲手胡乱写的东西,能看懂才怪!再附上代码吧:(我的小数据范围是暴力的)
#include <cmath> #include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; inline void Exgcd(LL a, LL b, LL &d, LL &x, LL &y) { if (!b) { d = a, x = 1, y = 0; } else { Exgcd(b, a % b, d, y, x), y -= x * (a / b); } } inline LL gcd(LL a, LL b) { return (!b) ? a : gcd(b, a % b); } inline LL Solve(LL a, LL b, LL c) { // ax=b(mod c) LL d, x, y; Exgcd(a, c, d, x, y); return (x + c) % c * b % c; } LL ksm(LL x, LL y, LL p) { LL res = 1, t = x; for(; y; y >>= 1) { if (y & 1) res = res * t % p; t = t * t % p; } return res; } const int mod = 13131; struct Hashset { int head[mod], next[40010], f[40010], v[40010], ind; void reset() { ind = 0; memset(head, -1, sizeof head); } void insert(int x, int _v) { int ins = x % mod; for(int j = head[ins]; j != -1; j = next[j]) if (f[j] == x) { v[j] = min(v[j], _v); return; } f[ind] = x, v[ind] = _v; next[ind] = head[ins], head[ins] = ind++; } int operator [] (const int &x) const { int ins = x % mod; for(int j = head[ins]; j != -1; j = next[j]) if (f[j] == x) return v[j]; return -1; } }S; int main() { LL A, B, C; LL i; while(scanf("%I64d%I64d%I64d", &C, &A, &B) == 3) { if (C <= 100) { LL d = 1; bool find = 0; for(i = 0; i < C; ++i) { if (d == B) { find = 1; printf("%I64d\n", i); break; } d = d * A % C; } if (!find) puts("no solution"); } else { int m = (int)sqrt(C); S.reset(); LL d = 1; for(i = 0; i < m; ++i) { S.insert(d, i); d = d * A % C; } bool find = 0; int ins; for(i = 0; i * m < C; ++i) { LL t = Solve(ksm(A, i * m, C), B, C); if ((ins = S[t]) != -1) { printf("%I64d\n", i * m + ins); find = 1; break; } } if (!find) puts("no solution"); } } return 0; }
POJ2417 Baby-Step-Gaint-Step 算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。