题目背景

众所周知，我们可以写一个 $O(n)$ 复杂度的 for 循环计算 $a^n\mod b$ 的值。

然而，现在 $n\le 10^{17}$。

$O(n)$ 的思路显然是要 TLE 的。

题目描述

优化方式有很多，这里讲一种和倍增思想有关的方法。

本质上其实是 对 $n$ 进行二进制分解的同时完成对 $a^n\mod b$ 的计算。

详细过程大概是这样的：

1. 算出 $n$ 的二进制形式在 $2^0$ 这一位上的取值，若为 $1$ 答案就乘 $a$。
2. 算出 $n$ 的二进制形式在 $2^1$ 这一位上的取值，若为 $1$ 答案就乘 $a^2$。
3. 算出 $n$ 的二进制形式在 $2^2$ 这一位上的取值，若为 $1$ 答案就乘 $a^4$。 。。。。。。

以此类推。

下面是一个函数，你需要补全函数内未填充的代码。

long long power(long long a, long long n, long long b) {
    // 计算 a 的 n 次方对 b 取模的结果，并存储至变量 ans
    long long ans = 1;
    while (n) {
        if (①) {
            ②
        }
        ③
    }
    return ans;
}

①② 处分别应填{{ select(1) }}。

• n % 2 == 0 ans = ans * a;
• n % 2 == 1 ans = ans * a;
• n & 1 ans = ans * a % b;
• n & (1 << a) ans = ans * a % b;

③ 处应填{{ select(2) }}。

• n >>= 1; a = a * a % b;
• a = a * a; n /= 2;
• n /= 2; a = (a + a) % b;
• n /= 2; a = a * a;