kcits970   1년 전

This cost me 2 hours of debugging to find out.

input:
1
0 0 1 1

expected:
Case #1: 0

 

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.

댓글을 작성하려면 로그인해야 합니다.