@[樱初音斗橡皮](/space/show?uid=66287) 你的龟速乘挂了。。。。。。
by RiverFun @ 2019-03-17 14:42:19
龟速乘初始值设为1是什么意思？
by RiverFun @ 2019-03-17 14:42:44
@[Steve_braveman](/space/show?uid=96570) 哦谢谢！！！！！QWQ从快幂改的，改出锅了。。。
by 樱初音斗橡皮 @ 2019-03-17 14:43:27
@[Sai_0511](/space/show?uid=114320) 感谢大佬QWQ
by 樱初音斗橡皮 @ 2019-03-17 14:43:56
@[樱初音斗橡皮](/space/show?uid=66287)
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
using std::cin;
using std::cout;
using std::endl;
long long fast_mul(long long x, long long y, long long p)
{
long long ans=0;
while (y)
{
if (y&1)
(ans+=x)%=p;
(x+=x)%=p;
y>>=1;
}
return ans;
}
long long fast_pow(long long base, long long ind, long long p)
{
long long ans=1;
while (ind)
{
if (ind&1)
(ans*=base)%=p;
(base*=base)%=p;
ind>>=1;
}
return ans;
}
long long k, m;
long long bsgs(long long a, long long b, long long p) //a^x%p==b
{
b%=p;
long long c=std::sqrt(p)+1;
long long a_c=fast_pow(a, c, p);
if (!a_c)
return !b ? 1 : -1;
std::map<long long, long long> mp;
for (long long j=0; j<c; ++j) //a^j*b
{
long long ans=fast_mul(fast_pow(a, j, p), b, p);
mp[ans]=j;
printf("add:%lld %lld\n", ans, j);
}
for (long long i=0; i<=c; ++i) //(a^c)^i
{
long long ans=fast_pow(a_c, i, p);
std::map<long long, long long>::iterator it;
it=mp.find(ans);
printf("find:%lld %lld\n", ans, i);
if (it!=mp.end())
{
long long j=mp[ans];
if (i*c>=j && ans >= 0)
return i*c-j;
}
}
return -1;
}
int main()
{
cin>>k>>m;
(k=9*k+1)%=m;
cout<<bsgs(10, k, m)<<endl;
return 0;
}
```
by Sai0511 @ 2019-03-17 14:44:44
帮您看了下，现在能过样例了。
by Sai0511 @ 2019-03-17 14:45:03
@[Sai_0511](/space/show?uid=114320) 全WA QWQ
by 樱初音斗橡皮 @ 2019-03-17 14:46:09
@[樱初音斗橡皮](/space/show?uid=66287) 我这里测出来80分啊。。 您是不是注释忘删了？
by Sai0511 @ 2019-03-17 14:46:45
@[樱初音斗橡皮](/space/show?uid=66287)
1:您的a不能%mod
2:
long long ans=fast_pow(a_c, i, b);
这里的b应该是p
by Sai0511 @ 2019-03-17 14:51:59
@[Sai_0511](/space/show?uid=114320) 对哦QWQ我总是犯垃圾错误耽误大佬时间。。。
by 樱初音斗橡皮 @ 2019-03-17 14:55:46