算法训练，一日一题

【python答案】
mod = 5218

def qpow(b):
    ans = 1
    a = 3
    if b < 0: return 1.0 / 3
    while b > 0:
        if b & 1:
            ans = (ans * a) % mod
        b >>= 1
        a = (a * a) % mod
    return ans% mod


product = 0
n = int(input())
if n % 3 == 0: product = qpow(int(n / 3))
if n % 3 == 1: product = qpow(int(n / 3) - 1) * 4
if n % 3 == 2: product = qpow(int(n / 3)) * 2
print(int(product) % mod)

【C答案】
#include<stdio.h>
#define M 5218
long long a[11]={0,1,2,3,4,6,9,12,18,27,36};
long long fastpower(long long m,long long n);
int main(){
	int i;
	long long n,ans=1;
	scanf("%lld",&n);
	if(n<=10){printf("%d",a[n]);
		return 0;}
	else{if(n%9==0){
			ans=fastpower(a[9],n/9);
			printf("%lld",ans%M);
			return 0;
		}else if(n%9==1){
			ans=fastpower(a[9],n/9-1);
			printf("%lld",36*ans%M);
			return 0;
		}
		else{ans=fastpower(a[9],n/9);
			printf("%lld",a[n%9]*ans%M);
			return 0;}}}
long long fastpower(long long m,long long n){
	long long ans=1;
	while(n){
		if(n&1)ans=ans*m%M;
		m=n>>=1;m*