题面
https://www.luogu.com.cn/problem/P2485
题解
对于T=1，快速幂即可。
对于T=2，exgcd即可。
重点是T=3，需要使用BSGS算法。
BSGS算法
用来快速求解形如({a^x}{equiv}r(mod p))的指数同余方程的算法，适用范围是(gcd(a,p)=1)。
由欧拉-费马定理可得(a^{phi(p)}{equiv}1(mod p))。下设(0<=x<{phi(p)})。
设置“间隔”(T),那么x一定可以表示成(iT-j)（其中(1<=j<=T)）的形式。下有
[a^{iT-j}{equiv}r{mod p}
]
[a^{iT}{equiv}r*a^j{mod p}
]
故只要某一个(a^{iT}(1<=i<={lceil{{phi(p)-1}over{T}} ceil}))以及某一个(r*a^j(1<=j<=T))相等，就得到了一个解(x=iT-j)。
实现时只需要将所有的(r*a^j)预处理好放入Hash表内，在计算(a^{iT})的时候同步查询就可以了。
计算(r*a^j)的时间复杂度为(O(T))，计算(a^{iT})的时间复杂度是(O({{phi(p)}over{T}}))，取(T=sqrt{phi(p)})即可保证总时间复杂度是(O(sqrt{phi(p)}))。
回本题
给出(y),(z),(p)，计算满足(y^x{equiv}z{mod{p}})的最小非负整数 (x)。
保证(p)是质数。
首先考虑(p|y)的情况，即({gcd}(y,p){ ot=}1)的情况，此时不能适用BSGS算法
- 1、(z=0)：(x=1)即可
- 2、(z=1)：(x=0)即可
- 3、others:无解
其他情况可以适用BSGS解决。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
inline ll read(){
ll s = 0,ww = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
return s * ww;
}
inline void write(ll x){
if(x < 0)putchar('-'),x = -x;
if(x > 9)write(x / 10);
putchar('0' + x % 10);
}
ll mod,g;
inline ll check(ll x){
return (x % mod + mod) % mod;
}
namespace ModCalc{
inline void Inc(ll &x,ll y,ll mod){
x += y;if(x >= mod)x -= mod;
}
inline void Dec(ll &x,ll y,ll mod){
x -= y;if(x < 0)x += mod;
}
inline ll Add(ll x,ll y,ll mod){
Inc(x,y,mod);return x;
}
inline ll Sub(ll x,ll y,ll mod){
Dec(x,y,mod);return x;
}
}
using namespace ModCalc;
inline ll power(ll a,ll n){
ll x = a,s = 1;
while(n){
if(n & 1)s = s * x % mod;
x = x * x % mod;
n >>= 1;
}
return s;
}
inline ll exgcd(ll a,ll &x,ll b,ll &y){
if(!b){
x = 1,y = 0;
return a;
}
ll g = exgcd(b,y,a%b,x);
y -= a / b * x;
return g;
}
map<ll,ll>M;
int main(){
ll T = read(),opt = read();
if(opt == 1){
while(T--){
ll a = read(),n = read();
mod = read();a %= mod;
write(power(a,n));putchar('
');
}
}
else if(opt == 2){
while(T--){
ll a = read(),r = read();
mod = read();
ll x,y;
ll g = exgcd(a,x,mod,y);
if(r % g != 0){
puts("Orz, I cannot find x!");
continue;
}
a /= g,r /= g,mod /= g;
x = check(x * r);
write(x);putchar('
');
}
}
else{
while(T--){
ll a = read(),r = read();
mod = read();a %= mod,r %= mod;
if(!a){
if(!r)puts("1");
else if(r == 1)puts("0");
else puts("Orz, I cannot find x!");
continue;
}
ll T = (ll)round(sqrt(mod));
ll a_T = power(a,T);
M.clear();
for(rg ll i = 1,cur = r * a % mod;i <= T;i++,cur = cur * a % mod)M[cur] = i;
ll flag = 0;
for(rg ll i = 1,cur = a_T;i * T - T <= mod - 2;i++,cur = cur * a_T % mod)if(M.count(cur)){
write(Sub(i*T%(mod-1),M[cur],mod-1)),putchar('
');
flag = 1;
break;
}
if(!flag)puts("Orz, I cannot find x!");
}
}
return 0;
}