C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 412K, 提交时间: 2022-10-19 12:56:18

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int get_phi(int x) {
    int s = 1;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) x /= i, s *= (i - 1);
        while (x % i == 0) {
            x /= i, s *= i;
        }
    }
    if (x > 1) s = s * (x - 1);
    return s;
}
ll qsm(ll a, ll b) {
    ll s = 1;
    while (b) {
        if (b & 1) s = s * a;
        a = a * a;
        b >>= 1;
    }
    return s;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int c, s;
        scanf("%d%d", &c, &s);
        ll ans = 0;
        for (int i = 1; i <= s / i; i++) {
            if (s % i == 0) {
                ans += get_phi(i) * qsm(c, s / i);
                if (i != s / i) ans += get_phi(s / i) * qsm(c, i);
            }
        }
        if (s & 1) ans += qsm(c, (s + 1) / 2) * s;
        else ans += (qsm(c, s / 2) + qsm(c, (s + 2) / 2)) / 2 * s;
        printf("%lld\n", ans / (2 * s));
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 400K, 提交时间: 2022-11-11 21:00:49

#include<bits/stdc++.h>  
using namespace std;  
typedef long long LL;
const int MOD = 1e9+7;
LL qmi(LL a,LL b){
	LL res = 1;
	while(b){
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}	
	return res;
}
int main(){ 
//  freopen("a.txt","r",stdin);
	int T;
	cin>>T;
	while(T--){
		LL n,k;
		cin>>k>>n;
		LL s = 0;
		for(int i = 0;i<n;++i){
			s+=qmi(k,__gcd(n,(LL)i));
		}
		LL ans = 0;
	//	cout<<s<<" "<<2*n<<'\n';
		if(n%2){
			ans = s+qmi(k,(n+1)/2)*n;
		}
		else{
			ans = s+qmi(k,n/2)*n/2+qmi(k,n/2+1)*n/2;
		}
		cout<<ans/2/n<<'\n';
	}
	return 0;
}