洛谷网校出版的《深入浅出程序设计竞赛》提高篇中把这道题改成了：给定 $a,c$，有 $q$ 次询问，每次询问给出 $b$，请你输出 $a^b \bmod c$。书上提到了这道题的 $O(q)$ 解法。及运用公式：

$a^b=(a^{\sqrt{c}})^{\left\lfloor\frac{b}{\sqrt{c}}\right\rfloor} \times a^{b \bmod \sqrt{c}}$

于是之用预处理 $(a^{\sqrt{c}})^i$ 和 $a^j$（$0 \le i \le 2\sqrt{c}$，$0 \le j \le \sqrt{c}$）即可做到 $O(q)$。

于是我编写了如下代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7;
int A[N], B[N];
/*
ai=a^{sqrt(c)}^i
bi=a^i
*/
int q, a, c;
int sqrtc;
int qpow(int a, int b)
{
	int res = 1, base = a;
	while (b)
	{
		if (b & 1) res *= a;
		base *= base;
		b >>= 1;
	}
	return res;
}
void init()
{
	int f = qpow(a, sqrtc);
	A[0] = B[0] = 1;
	for (int i = 1; i <= (sqrtc << 1) + 1; i ++)
		A[i] = A[i - 1] * f % c;
	for (int i = 1; i <= sqrtc + 1; i ++)
		B[i] = B[i - 1] * a % c;
}
signed main()
{
	cin >> q >> a >> c;
	sqrtc = sqrt(c);
	init();
	while (q --)
	{
		int b;
		cin >> b;
		cout << ((A[b / sqrtc] % c) * (B[b % sqrtc] % c)) % c << endl;
	}
	return 0;
}

输入：

2 2 5
3
4

应输出：

3
1

但是我的程序输出了:

4
4

请问问题出在哪里？