C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 456K, 提交时间: 2020-08-07 15:04:40

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int MAX=1e6+100;
ll f[MAX];
ll qmod(ll x,ll k,ll mod) {
	x%=mod; 
	ll cnt=1;
	while (k) {
		if (k&1) cnt=cnt*x%mod;
		k>>=1;
		x=x*x%mod;
	} 
	return cnt;
}
int main() {
	ll t,a,b,c,i,p;
	cin>>t;
	while (t--) {
		cin>>a>>b>>c;
		f[0]=0; f[1]=1;
		for (i=2;i<=MAX;i++) {
			f[i]=(f[i-1]+f[i-2])%c;
			if (f[i-1]==0&&f[i]==1) break;
		}
		p=qmod(a,b,i-1);
		cout<<f[p]<<endl;
	}
}

C++ 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2022-07-08 17:43:52

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define MAXN 100005
int t,i,c,f[100005];
ll a,b;
int Pow(ll x,ll y,int z)
{
	x%=z;
	int s=1;
	for(;y;y>>=1,x=x*x%z)if(y&1)s=s*x%z;
	return s;
}
int main()
{
	scanf("%d",&t);
	f[1]=1;
	while(t--)
	{
		cin>>a>>b>>c;
		for(i=1;;i++)
		{
			f[i+1]=f[i]+f[i-1];
			if(f[i+1]>=c)f[i+1]-=c;
			if(!f[i]&&f[i+1]==1)break;
		}
		printf("%d\n",f[Pow(a,b,i)]);
	}
	return 0;
}