C++(g++ 7.5.0) 解法, 执行用时: 1100ms, 内存消耗: 552K, 提交时间: 2022-10-17 13:08:34

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

C++(clang++ 11.0.1) 解法, 执行用时: 457ms, 内存消耗: 536K, 提交时间: 2022-07-31 09:04:13

#include<bits/stdc++.h>
#define ll long long
using namespace std ;
int T,n,p ;
int qsm(int a,int b,int mod)
{
	int ans=1 ;
	while(b)
	{
		if(b&1) ans=(ll)ans*a%mod ;
		a=(ll)a*a%mod ; b>>=1 ;
	}
	return ans ;
}
int phi(int n)
{
	int ans=n ;
	for(int i=2;i*i<=n;++i)
		if(n%i==0)
		{
			ans=ans/i*(i-1) ;
			while(n%i==0) n/=i ;
		}
	if(n>1) ans=ans/n*(n-1) ;
	return ans ;
}
int main()
{
	cin>>T ;
	while(T--)
	{
		cin>>n>>p ;
		int ans=0 ;
		for(int d=1;d*d<=n;d++)
			if(n%d==0)
			{
				ans+=(ll)phi(d)*qsm(n,n/d-1,p)%p ;
				if(ans>=p) ans-=p ;
				if(d*d!=n)
				{
					ans+=(ll)phi(n/d)*qsm(n,d-1,p)%p ;
					if(ans>=p) ans-=p ;
				}
			}
		cout<<ans<<'\n' ;
	}
	return 0 ;
}