Java(javac 1.8) 解法, 执行用时: 1121ms, 内存消耗: 28492K, 提交时间: 2019-04-26 16:56:00

import java.util.*;
import java.math.*;
public class Main {
	public static void main(String[] args)
	{
		Scanner in=new Scanner(System.in);
		int T=in.nextInt();
		for(int i=1; i<=T; i++)
		{
			BigInteger n=in.nextBigInteger(), p=in.nextBigInteger(), ko=new BigInteger("4"), on=new BigInteger("1");
			System.out.println(ko.modPow(n, p).subtract(on).add(p).remainder(p));
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 95ms, 内存消耗: 740K, 提交时间: 2019-04-21 15:32:31

#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	char s[100005];
	scanf("%d",&T);
	while(T--){
		long long p;
		scanf("%s%lld",&s,&p);
		int l1=strlen(s);
		int b=4;
		long long ans=1;
		for(int i=l1-1;i>=0;i--){
			for(int j=0;j<s[i]-'0';j++)
				ans=ans*b%p;
			int a=b;
			for(int i=1;i<10;i++)
				a=1ll*a*b%p;
			b=a;
		}
		printf("%d\n",(ans+p-1)%p);
	}
	
}

pypy3(pypy3.6.1) 解法, 执行用时: 145ms, 内存消耗: 20888K, 提交时间: 2020-10-23 20:45:37

t=int(input())
for i in range(t) :
    ans=1
    n=int(input())
    mod=int(input())
    print((pow(4,n,mod)-1+mod)%mod)

Python3(3.5.2) 解法, 执行用时: 200ms, 内存消耗: 4328K, 提交时间: 2019-04-24 10:27:15

import math;
t=int(input());
while t:
 n=int(input());
 p=int(input());
 print((pow(4,n,p)-1+p)%p);
 t-=1;