C++(g++ 7.5.0) 解法, 执行用时: 55ms, 内存消耗: 532K, 提交时间: 2023-06-08 20:05:25

#include <iostream>
#include <algorithm>

using i64 = long long;

using namespace std;

const int mod = 19260817;

int n, m;

int qpow(i64 a, i64 b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return res;
}

int phi(int x) {
  int res = x;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) x /= i;
      res = res / i * (i - 1);
    }
  }
  if (x > 1) res = res / x * (x - 1);
  return res;
}

int calc(int n) {
  int res = 0;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res = (res + 1ll * phi(i) * qpow(m, n / i) % mod) % mod;
      if (i * i != n) {
        res = (res + 1ll * phi(n / i) * qpow(m, i) % mod) % mod;
      }
    }
  }
  return 1ll * res * qpow(n, mod - 2) % mod;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    m = 1ll * m * (m + 1) / 2 % mod;
    cout << calc(n) << '\n';
  }
  return 0;
}

C++14(g++5.4) 解法, 执行用时: 112ms, 内存消耗: 536K, 提交时间: 2019-11-25 19:26:24

#include<bits/stdc++.h>
#include<tr1/unordered_map>
typedef long long ll;
using namespace std;
const int mod=19260817;
int T;
ll k,n;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll n)
{
	ll res=1;
	while(n)
	{
		if(n&1)	res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}
ll euler(int n)
{
	ll res=n;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			res=res/i*(i-1);
			while(n%i==0)	n/=i;
		}
	}
	if(n>1)	res=res/n*(n-1);
	return res;
}
ll solve(ll n,ll k)
{
	ll ans=0;
	for(int i=1;i*i<=n;i++)
	{
		if(n%i)	continue;
		ans=(ans+euler(i)*qpow(k,n/i)%mod)%mod;
		if(i*i!=n)	ans=(ans+euler(n/i)*qpow(k,i)%mod)%mod;
	}
	ans=ans*qpow(n,mod-2)%mod;
	return ans;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&k);
		printf("%lld\n",solve(n,k*(k+1)/2%mod));
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 49ms, 内存消耗: 652K, 提交时间: 2019-11-24 19:46:56

#include<bits/stdc++.h>
using namespace std;
const int p=19260817;
int t,n,m,ans;
int power(int x,int y){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%p)if(y&1)z=1ll*z*x%p;
    return z;
}
int phi(int x){
    int z=x;
    for(int i=2;i*i<=x;i++)if(x%i==0){
        z=z/i*(i-1);
        while(x%i==0)x/=i;
    }
    if(x!=1)z=z/x*(x-1);
    return z;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);ans=0;m=1ll*m*(m+1)/2%p;
        for(int i=1;i*i<=n;i++)if(n%i==0){
            ans=(ans+1ll*power(m,i)*phi(n/i))%p;
            if(i*i!=n)ans=(ans+1ll*power(m,n/i)*phi(i))%p;
        }
        printf("%d\n",1ll*ans*power(n,p-2)%p);
    }
    return 0;
}