C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 612K, 提交时间: 2019-05-25 12:58:07

#include <iostream>
using namespace std;
int t;
int n,q,p;
int qpow(int a,int b){
	int c=1;
	while (b){
		if (b&1)
			c=1ll*a*c%p;
		b>>=1;
		a=1ll*a*a%p;
	}
	return c;
}
int solve(int l){
	if (l==1) return q;
	int mid=l>>1;
	int p1=solve(mid);
	if (l&1)
		return (1ll*p1+1ll*qpow(q,mid)*p1%p+qpow(q,l))%p;
	return (1ll*p1+1ll*qpow(q,mid)*p1%p)%p;
}
int main(){
	cin >> t;
	while (t--){
		cin >> q >> n >> p;
		cout << solve(n) << '\n';
	}
}

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 504K, 提交时间: 2021-05-01 15:44:40

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,mod;
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;
}
ll sum(ll p,ll k){
	if(k==1) return p%mod;
	if(k%2==1) return (sum(p,k-1)  +qpow(p,k))%mod;
	return (1+qpow(p,k/2)) * sum(p,k/2) %mod; 
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		cin>>q>>n>>mod;
		cout<<sum(q,n) %mod<<endl;
	}
}

Python3(3.9) 解法, 执行用时: 20ms, 内存消耗: 2680K, 提交时间: 2020-10-31 15:36:11

T = int(input())
for i in range(T):
    q, n, p = map(int, input().split())
    mod = (q - 1) * p
    ans = (q * (pow(q, n, mod) - 1 + mod) % mod) // (q - 1)
    print(ans)