y=0好像用BSGS也没问题?(雾)
还有不要在讨论区发题解
by 142857cs @ 2020-01-14 20:37:12
asdfasdfasdfasdf
by Luogu_Monkey @ 2020-01-14 20:38:55
@[142857cs](/user/35760)
我不能保证所有的BSGS写法都有问题,但至少如下这份我认为比较一般的BSGS写法是有问题的:
```
int p,y,z;
map<int,int> mp;
int BSGS(){
if(z==1) return 0;
int m=sqrt(p)+1;
mp.clear();
int t=z;
for(int i=0;i<m;++i,t=t*y%p) mp[t]=i; //mp[0]最后会等于m-1
t=1;
for(int i=1;i<=m;++i) t=t*y%p;
for(int i=1,s=t;i<=m+1;++i,s=s*t%p) //i=1时退出循环 ,返回值为i*m-(m-1)=1
if(mp.count(s)) return i*m-mp[s];
return -1;
}
```
注释表明,当$y=0$时,对于任何$z\neq1$返回值都会是$1$。暂且不论当$z=0$时解为$0$还是$1$值得斟酌,重点是漏判了所有$z\neq0$的无解情况。
所以当$y=0$时最好还是写特判吧$qwq$
我很抱歉,我以为这道题的核心还是BSGS算法,帖子只是提出了一些细节上的问题,也不算题解吧?
by 青君 @ 2020-01-15 12:19:42
@[青君](/user/118092) emmm。。。有的写法是对的,有的写法不对。。。这已经不是BSGS的正常使用了
by 142857cs @ 2020-01-15 13:16:56