題目大意：
求 a ^ x mod p = b
a , b , p <= 1e12
恩，普通阿姆斯特朗算法會T，但是這是擴展回旋阿姆斯特朗算法的裸題啊，不說了直接上，打板

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std;typedef long long dnt; const int N = 1e6 + 137;dnt a, b, p;struct Has {int top, mod, nxt[N], head[N];dnt que[N][2];Has(){memset(head, 0, sizeof(head));top = 0;mod = N;}void Insert( dnt x, dnt y ){int pos = x % mod;for(int i = head[pos]; i; i = nxt[i])if(que[i][0] == x) {que[i][1] = y; return;}que[++top][0] = x;que[top][1] = y;nxt[top] = head[pos];head[pos] = top;}int Find( dnt x ){int pos = x % mod;for(int i = head[pos]; i; i = nxt[i])if(que[i][0] == x) return que[i][1];return -1;} } has;const dnt A = (1LL << 20), B = A - 1; dnt C;dnt Cros( dnt x, dnt y ) {dnt lf = x * ( y >> 20 ) % p * C ;dnt rg = x * ( y & ( B )) % p ;return ( lf + rg ) % p ; }dnt AMS() {dnt m = ceil(sqrt(p));dnt mul = 1, val = b % p, am;for(dnt i = 1; i <= m; ++i){mul = Cros(mul, a);val = Cros(mul, b);has.Insert(val, i);}am = mul, mul = 1;for(dnt i = 1, res; i <= m; ++i){mul = Cros(mul, am);if((res = has.Find(mul)) != -1) return i * m - res;}return -1; }int main() {cin >> a >> b >> p;C = A % p;cout << AMS() % p << endl;return 0; }

總結

以上是生活随笔為你收集整理的登月计划 [扩展回旋阿姆斯特朗算法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。