@[ShadderLeave](/user/215697)
您能贴出来您TLE的代码吗？
by metaphysis @ 2020-04-06 23:07:56
@[metaphysis](/user/333388)
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL A,B,C;
struct Hash_table{
static const LL MOD=1999997;
LL Hash[MOD],V[MOD],stk[MOD],top;
//Hash_table() {memset(Hash,-1,sizeof(Hash));}
inline void Insert(LL val,LL mi)
{
LL h=val%MOD;
while(Hash[h]&&Hash[h]!=val) h++;
Hash[h]=val;V[h]=mi;
stk[++top]=h;
return ;
}
inline LL find(LL val)
{
LL h=val%MOD;
while(Hash[h]&&Hash[h]!=val) h++;
return Hash[h]==val?V[h]:-1;
}
}H;
inline LL fast_pow(LL b,LL k)
{
LL s=1;
if(k<0) puts("CZAKIOI");
while(k)
{
if(k&1) s=(s*b)%C;
b=(b*b)%C;
k>>=1;
}
return s;
}
LL N;
int main()
{
scanf("%lld%lld",&A,&C);
LL sqrtm=ceil(sqrt(C));
LL t=1,ti=fast_pow(A,sqrtm);
for(LL i=0;i<=sqrtm;i++)
{
H.Insert(t,i*sqrtm);
t=t*ti%C;
}
scanf("%lld",&N);
LL x,y,ans;
for(int i=1;i<=N;i++)
{
scanf("%lld%lld",&x,&y);
t=x;
for(int j=0;j<sqrtm;j++)
{
if((ans=H.find(t))!=-1)
{
ans-=j;
printf("%lld\n",fast_pow(y,ans));
break;
}
t=t*A%C;
}
}
return 0;
}
```
by LeavingZ @ 2020-04-07 06:31:36
@[ShadderLeave](/user/215697)
您的代码中，快速幂出现了负值，因为当把快速幂修改为：
```
inline LL fast_pow(LL b,LL k)
{
LL s=1;
// if(k<0) puts("CZAKIOI");
assert(k >= 0);
while(k)
{
if(k&1) s=(s*b)%C;
b=(b*b)%C;
k>>=1;
}
return s;
}
```
第二个测试点RE，其他测试点AC。之所以您用：
```
if(k<0) puts("CZAKIOI");
```
就得出了“而且判断过了快速幂没有出负指数”的结论，是因为没有立即返回。如果将快速幂修改为：
```
inline LL fast_pow(LL b,LL k)
{
LL s=1;
if(k<0) { puts("CZAKIOI"); return s; }
while(k)
{
if(k&1) s=(s*b)%C;
b=(b*b)%C;
k>>=1;
}
return s;
}
```
则第二个测试点WA，其他测试点AC。
by metaphysis @ 2020-04-07 07:13:59
@[metaphysis](/user/333388) 谢谢您
by LeavingZ @ 2020-04-07 08:02:04