I repeatedly got WA verdicts due to my badly written exponentiation function.
ll raise(ll base, ll exp, ll mod)
{
ll res = 1;
while (exp)
{
if (exp & 1)
{
res *= base;
res %= mod;
exp ^= 1;
}
else
{
base *= base;
base %= mod;
exp >>= 1;
}
}
return res;
}
The problem arises when exp = 0 and mod = 1. In this case, the raise function returns 1 (when the correct return value is 0).
The corrected implementation returns `res` % `mod` instead of just `res`. Normally this isn't necessary because the mod is usually sufficiently large, but it becomes an exception here.
kcits970 1년 전
This cost me 2 hours of debugging to find out.
I repeatedly got WA verdicts due to my badly written exponentiation function.
ll raise(ll base, ll exp, ll mod) { ll res = 1; while (exp) { if (exp & 1) { res *= base; res %= mod; exp ^= 1; } else { base *= base; base %= mod; exp >>= 1; } } return res; }The problem arises when exp = 0 and mod = 1. In this case, the raise function returns 1 (when the correct return value is 0).
The corrected implementation returns `res` % `mod` instead of just `res`. Normally this isn't necessary because the mod is usually sufficiently large, but it becomes an exception here.