C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 468K, 提交时间: 2023-05-24 17:17:37

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

i64 power(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    i64 ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += power(3, gcd(n, i));
    }
    if (n & 1) {
        ans += n * power(3, (n + 1) / 2);
    } else {
        ans += n / 2 * power(3, n / 2);
        ans += n / 2 * power(3, (n + 2) / 2);
    }
    ans /= 2 * n;
    cout << ans << '\n';
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 440K, 提交时间: 2022-05-25 21:57:49

#include<iostream>
#include<math.h>
using namespace std;
typedef long long LL;
LL gcd(LL a ,LL b)
{
    return b ? gcd(b , a % b) : a;  
}

int main()
{
    LL n;
    cin>>n;

    LL ans=0;
    for(LL i=1;i<=n;i++)
    {
        LL k=gcd(i,n);
        ans=ans+pow(3,k);           
    }
    if(n%2==0)
        ans=ans+(n*pow(3,n/2)+3*n*pow(3,n/2))/2;
    else
        ans=ans+n*pow(3,(n+1)/2);
    ans=ans/(2*n);
    cout<<ans<<endl;
    return 0;
    
}

Python3 解法, 执行用时: 44ms, 内存消耗: 4636K, 提交时间: 2022-02-01 11:07:20

import math
n=int(input())

ans=0
for i in range(1,n+1):
    ans+=3**math.gcd(i,n)

if(n%2==0):
    ans+=2*n*(3**(n//2))
else:
    ans+=n*(3**((n-1)//2+1))

ans//=(2*n)

print(ans)