C++11(clang++ 3.9) 解法, 执行用时: 90ms, 内存消耗: 676K, 提交时间: 2019-07-14 20:47:26

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const ll R_2 = (MOD + 1) / 2;
const ll R_6 = (MOD + 1) / 6;

int n, m;
vector<int> V;
ll ans;

ll cal(int res) {
	ll r = n / res;
	ll ans = r * (r + 1) % MOD * (2 * r + 1) % MOD * R_6 % MOD * res % MOD * res % MOD + r * (r + 1) % MOD * R_2 % MOD * res;
	return ans;
}

void dfs(int pre, int res, int mu) {
	if (pre >= V.size()) {
		ans = (ans + cal(res) * 1LL * mu) % MOD;
		return;
	}
	dfs(pre + 1, res, mu);
	dfs(pre + 1, res * V[pre], -mu);
}

void solve() {
	V.clear();
	for (int i = 2; i * i <= m; i++) {
		if (m % i == 0) {
			V.push_back(i);
			while (m % i == 0) m /= i;
		}
	}
	if (m > 1) V.push_back(m);
	ans = 0;
	dfs(0, 1, 1);
	ans = (ans % MOD + MOD) % MOD;
	printf("%lld\n", ans);
}

int main() {
	while (~scanf("%d%d", &n, &m)) {
		solve();
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 310ms, 内存消耗: 736K, 提交时间: 2019-07-15 11:02:02

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=3e5+10;
const int mod=1e9+7;
ll n,m,inv_6=(mod+1)/6,inv_2=(mod+1)/2;
int s[N/10];
ll cal(ll k,ll c)
{
	return k*k%mod*c%mod*(c+1)%mod*(2*c+1)%mod*inv_6%mod+k*c%mod*(c+1)%mod*inv_2%mod;
}
int main()
{
	while(~scanf("%lld%lld",&n,&m))
	{
		int cnt=0;
		for(int i=2;i*i<=m;i++)
		{
			if(m%i==0) 
			{
				s[cnt++]=i;
			    while(m%i==0) m/=i; 
			}
		}
		if(m>1)s[cnt++]=m; 
		ll k=1,ans=0;
		for(int i=1;i<1<<cnt;i++)
		{
			ll sum=0,k=1;
			for(int j=0;j<cnt;j++)
			 if(i>>j&1) sum++,k*=s[j]; 
			 
			if(sum&1)
			{
				ll c=n/k;
				ans=(ans+cal(k,c))%mod;
			} 
			else
			{
				ll c=n/k;
				ans=(ans-cal(k,c)+mod)%mod;
			}
	    }
		ans=(cal(1,n)-ans+mod)%mod;
		cout<<ans<<endl;
	} 
	return 0;
}