C++(g++ 7.5.0) 解法, 执行用时: 292ms, 内存消耗: 432K, 提交时间: 2022-12-07 20:52:34

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll pow1(ll x,ll y,ll mod)
{
    ll sum=1;
    while(y)
    {
        if(y&1)sum=sum*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return sum;
}
ll inv(ll x,ll mod)
{
    return pow1(x,mod-2,mod);
}
int main()
{
    int t;
    cin>>t;
    ll mod=1e9+7;
    ll ans;
    while(t--)
    {
        ll n,m;
        ans=0;
        cin>>n>>m;
        for(ll i=1;i<=m;i++)
            ans+=pow1(n,__gcd(m,i),mod);
        if(m&1)ans+=m*pow1(n,m/2+1,mod)%mod;
        else
        {
            ans+=m/2*pow1(n,m/2,mod)%mod;
            ans+=m/2*pow1(n,m/2+1,mod)%mod;
        }
        ans%=mod;
        ans=ans*inv(m*2,mod);
        cout<<ans%mod<<endl;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 351ms, 内存消耗: 432K, 提交时间: 2018-02-06 20:53:35

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e9+7;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll Pow(ll a,ll x){
    ll res=1;
    while(x){
        if(x&1) res=res*a%M;
        a=a*a%M;
        x>>=1;
    }
    return res%M;
}
int main(){
    ll t,n,m;
    for(scanf("%lld",&t);t--;){
        scanf("%lld%lld",&n,&m);
        ll ans=0;
        if(m & 1) ans=m*Pow(n,m/2+1)%M;
        else ans=((m/2*Pow(n,m/2))%M+(m/2*Pow(n,m/2+1))%M)%M;
        for(int i=0;i<m;++i) ans=(ans+Pow(n,gcd(m,i)))%M;
        printf("%lld\n",ans*Pow(m*2%M,M-2)%M);
    }
    return 0;
}