修改2020.12.24
第1种较朴素的方法
根据题意要求满足$a^x \equiv b \pmod p$。由于p是质数,$a\lt p$,满足费马小定理$a^{p-1}\equiv 1 \pmod p$,即$a^{x\, mod\, (p-1)}\equiv a^x \pmod p$,如果存在一个x,那么必然在[1,p-1]之间,因为余数b>=2,所以l肯定不是0,故l从1开始。
那么最朴素的方法就是,x从1到p-1枚举,看看哪个符合条件,满足$a^x \equiv b \pmod p$就可以了。但是p的范围到$10^9$,显然这个做法不能满分。
把$1,2,3,…,p-1$这些数,换一个枚举的方法,把他们变成下面这个形式:
设$T=\lceil \sqrt p \rceil$,上取整是为了保证答案在遍历的区间内,让这个区间稍微大一点,不漏数。
1, 2, 3, ..., T-1, T,
T+1, T+2, T+3, ..., T+T-1 2T,
2T+1, 2T+2, 2T+3, ..., 2T+T-1, 3T,
.
.
.
(T-1)T+1, (T-1)T+2, (T-1)T+3, ..., (T-1)T+T-1, TT
最后的 $TT>=P$,显然等于把幂 $x$ 拆成 $x=im+j$ 这样的形式。推出:$a^{im}\equiv \frac{b}{a^j} \pmod p$,继续推出:$a^{im}\equiv b\cdot inv(a^j) \pmod p$
数据的存放2种选择
1、放到set里面。
数论题目要严格关注数据的大小,把数据对p取余后,和b进行比较,如果不等,放到set里面。如果相等,说明找到了,对应的i就是幂,返回就ok。然后,再依次求出$a^{im}$的大小,对p求余后和b比较,不同就continue,相同说明找到了答案所在行,然后一个一个的枚举比对找到j参数,再根据$x=im+j$还原后,返回x就行了。
2、放到map里面。
放入map和放入set相同,不同就是找到行后,就直接$x=im+j$计算就行。
说起来简单,做起来很啰嗦,还需要多写几遍才能掌握。
问为啥要到$\sqrt p$?
答:把一个线性的x到p-1拆成一个矩阵,只有正方形才是长和宽最短的方法,所以用$\sqrt p$。
数论题就是三个字:拆、拆、拆
放入set的写法
#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
int a,b,p;
LL qmi(LL a,LL b){
LL ans=1%p;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
void exgcd(int a,int b,LL &x,LL &y){
if(!b) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
LL inv(int a){
LL x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
LL bsgs(int a,int b){
static set<LL> S;
S.clear();
LL sp=ceil(sqrt(p));
LL t=1; //a^j = b * inv(a^{im}) (mod p),先放入S的是左边的a^j
for(int i=1;i<=sp;i++){
t=t*a%p;
if(t!=b) S.insert(t);
else return i;
}
for(int i=1;i<=sp;i++){
LL now=b*inv(qmi(a,sp*i))%p;
if(!S.count(now)) continue;
for(LL j=sp*i,v=qmi(a,j);;j++){
if(v==b) return j;
v=v*a%p;
}
}
return -1;
}
int main(){
scanf("%d%d%d",&p,&a,&b);
LL r=bsgs(a,b);
if(r<0) puts("no solution");
else printf("%lld\n",r);
return 0;
}
放入map的写法
放入map更简单一点,代码大部分都相同,就是bsgs函数有一点不同。
LL bsgs(int a,int b){
map<LL,LL> mp;
LL sp=ceil(sqrt(p));
LL t=1;
for(int i=1;i<=sp;i++){
t=t*a%p;
if(t!=b) mp[t]=i;
else return i;
}
for(int i=1;i<=sp;i++){
LL now=b*inv(qmi(a,sp*i))%p;
if(!mp.count(now)) continue;
LL ans=i*sp+mp[now];
return ans;
}
return -1;
}
第3种方法
第1,2种方法,都是把x拆成$x=im+j$,这样 j 移到右边就是除法了,所以需要逆元,如果变成$x=im-j$,这样移到右边就是乘法,就不用乘法逆元了,等式变成$a^{im} \equiv a^j \cdot b \pmod p $
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
LL a,b,p;
LL qmi(LL a,LL b){
LL ans=1%p;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
LL bsgs(LL a,LL b){ //a^x = b (mod p)
static map<LL,LL> mp;
LL sp=sqrt(p);
LL t=b; //a^{im} = b * a^j (mod p) 先把右边 b * a^j 放入map
for(int i=1;i<=sp;i++){
t=t*a%p;
mp[t]=i;
}
a=qmi(a,sp),t=1;
for(int i=1;i<=sp;i++){
t=t*a%p;
if(mp.count(t)){
LL ans=i*sp-mp[t];
return ans;
}
}
return -1;
}
int main(){
scanf("%lld%lld%lld",&p,&a,&b);
LL r=bsgs(a,b);
if(r>0) printf("%lld\n",r);
else puts("no solution");
return 0;
}