C++(g++ 7.5.0) 解法, 执行用时: 1542ms, 内存消耗: 42408K, 提交时间: 2023-04-27 17:16:06

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll inv_deg[300007], depth[300007], dp1[300007], dp2[300007];
vector<int> v[300007];

inline void init(int n){
	for (int i = 1; i * 2 <= n; i++){
		for (int j = i * 2; j <= n; j += i){
			v[j].push_back(i);
		}
	}
}

inline ll quick_pow(ll x, ll p, ll mod){
	ll ans = 1;
	while (p){
		if (p & 1) ans = ans * x % mod;
		x = x * x % mod;
		p >>= 1;
	}
	return ans;
}

int main(){
	int n, p;
	ll ans = 0;
	cin >> n >> p;
	init(n);
	for (int i = 1; i <= n; i++){
		inv_deg[i] = quick_pow(v[i].size(), p - 2, p);
	}
	depth[1] = 1;
	for (int i = 2; i <= n; i++){
		int size = v[i].size();
		for (int j = 0; j < size; j++){
			depth[i] = (depth[i] + depth[v[i][j]]) % p;
		}
		depth[i] = (depth[i] * inv_deg[i] % p + 1) % p;
	}
	for (int i = n; i >= 1; i--){
		for (int j = i; j <= n; j += i){
			dp1[j] = 0;
		}
		dp1[i] = 1;
		for (int j = i; j <= n; j += i){
			if (j != i) dp1[j] = dp1[j] * inv_deg[j] % p;
			dp2[i] = (dp2[i] + dp1[j]) % p;
			for (int k = j * 2; k <= n; k += j){
				dp1[k] = (dp1[k] + dp1[j]) % p;
			}
		}
		dp2[i] = dp2[i] * dp2[i] % p;
		for (int j = i * 2; j <= n; j += i){
			dp2[i] = ((dp2[i] - dp1[j] * dp1[j] % p * dp2[j] % p) % p + p) % p;
		}
	}
	for (int i = 1; i <= n; i++){
		ans = ((ans + depth[i] * (n - dp2[i]) % p) % p + p) % p;
	}
	cout << ans * 2 % p;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 293ms, 内存消耗: 6288K, 提交时间: 2023-04-27 19:01:26

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,mod;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline void Add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
int inv[N],dep[N],deg[N];
int f[N],g[N];
int main(){
	cin>>n>>mod;
	inv[1]=1;
	for(int i=2;i<=n;i++){
		inv[i]=mul(inv[mod%i],mod-mod/i);
		deg[i]=1;
	}
	for(int i=2;i<=n;i++){
		dep[i]=mul(dep[i],inv[deg[i]])+1;
		for(int j=i<<1;j<=n;j+=i)
			Add(dep[j],dep[i]),deg[j]++;
	}
	for(int i=n;i>=2;i--){
		for(int j=i;j<=n;j+=i)g[j]=0;
		g[i]=1;
		for(int j=i;j<=n;j+=i){
			if(j>i)g[j]=mul(g[j],inv[deg[j]]);
			for(int k=j<<1;k<=n;k+=j)Add(g[k],g[j]);
			Add(f[i],g[j]);
		}
		f[i]=mul(f[i],f[i]);
		for(int j=i<<1;j<=n;j+=i)f[i]=(f[i]-mod-1ll*f[j]*g[j]%mod*g[j])%mod+mod;
	}
	int ans=0;
	for(int i=2;i<=n;i++){
		ans=(ans+2ll*(n-f[i]-mod)*dep[i]-mod)%mod+mod;
	}
	cout<<ans<<endl;
	return 0;
}