简答题
适中
#24830
拆分
拆分

答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 1000000000;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
if (n == 2) {
puts("2");
continue;
}
if (n == 3) {
puts("3");
continue;
}
int r = n % 3;
int q = n / 3;
ll ans;
if (r == 0) {
ans = qpow(3, q);
} else if (r == 1) {
ans = qpow(3, q - 1) * 4 % mod;
} else { // r == 2
ans = qpow(3, q) * 2 % mod;
}
printf("%lld\n", ans);
}
return 0;
}</pre>
这道题暂未补解析。