本文共 1112 字，大约阅读时间需要 3 分钟。

一、题目描述

二、算法分析说明与代码编写指导

三、AC 代码

#include
   
    #include
    
     #include
     
      #pragma warning(disable:4996)using namespace std;unsigned long long a, b, p, x;template
      
        inline _Ty PowerMod(_Ty radix, _Ty exp, const _Ty& mod) {
   	_Ty ans = 1; radix %= mod;	while (exp) {
   		if (exp & 1)ans = (ans * radix) % mod;		exp >>= 1, radix = (radix * radix) % mod;	}	return ans % mod;}//Solve pow(a, x) ≡ b (% p) for x, GCD(a, p) = 1template
       
         inline _Ty bsgs(const _Ty& a, const _Ty& b, const _Ty& p) {
   	static unordered_map<_Ty, _Ty> u; pair<_Ty, _Ty> q(b % p, 0); _Ty m = ceil(sqrt(p)), L = 1 % p;	const _Ty fk = a % p, fi = PowerMod(a, m, p); static typename unordered_map<_Ty, _Ty>::iterator I;	u.clear(), u.emplace(q);	for (q.second = 1; q.second <= m; ++q.second) {
    q.first = q.first * fk % p, u.emplace(q); }	for (_Ty i = 1; i <= m; ++i) {
    L = L * fi % p, I = u.find(L); if (I != u.end())return i * m - I->second; }	return -1;}int main() {
   	scanf("%llu%llu%llu", &p, &a, &b);	x = bsgs(a, b, p);	if (x != -1)printf("%llu\n", x);	else puts("no solution");	return 0;}
       
      
     
    
   

转载地址：http://gotez.baihongyu.com/