C++(g++ 7.5.0) 解法, 执行用时: 1544ms, 内存消耗: 1976K, 提交时间: 2022-11-18 11:39:02

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 50000 + 10, mod = 1e9 + 7;

int primes[N], mu[N], cnt;
bool st[N];
int s[N];
void get_mu()
{
	mu[1] = 1;
	for(int i = 2; i <= N; i++)
	{
		if(!st[i])primes[++cnt] = i, mu[i] = -1;
		for(int j = 1; j <= cnt && primes[j] <= N / i; j++)
		{
			int x = primes[j] * i;
			st[x] = 1;
			if(i % primes[j] == 0)break;
			mu[x] = -mu[i];
		}
	}
	for(int i = 1; i <= N; i++)mu[i] += mu[i - 1];
}

//预处理出每一个块  求约数的个数
void init()
{
	for(int k = 1; k <= N; k++)
	{
		int ans = 0;
		for(int l = 1, r = 0; l <= k; l = r + 1)
		{
			r = k / (k / l);
			ans += (r - l + 1) * (k / l);
		}
		s[k] = ans;
	}
}

void solve()
{
	int n, m;
	cin >> n >> m;
	int ans = 0;
	if(n > m)swap(n, m);
	for(int i = 1, j = 0; i <= n; i = j + 1)
	{
		j = min(n / (n / i), m / (m / i));
		ans += (mu[j] - mu[i - 1]) * s[n / i] * s[m / i];
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T = 1;
	init();
	get_mu();
	cin >> T;
	while(T--)solve();
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 831ms, 内存消耗: 1760K, 提交时间: 2019-08-05 11:07:38

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N = 50000 + 10;
bool vis[N];
vector<int>prime;
int mu[N+10],sum[N+10],f[N+10];
void init(){
	mu[1] = 1;
	for(int i=2;i<N;i++){
		if(!vis[i]){	prime.push_back(i);		mu[i] = -1;	}
		for(int j=0;j<prime.size()&&i*prime[j]<N;j++){
			vis[i*prime[j]] = true;
			if(i % prime[j] == 0){	mu[i*prime[j]] = 0;	break;	}
			mu[i*prime[j]] = -mu[i];
		}
	}
	for(int i=1;i<N;i++)	sum[i] = sum[i-1] + mu[i];
	for(int n=1;n<N;n++){
		for(int i=1;i<=n;i++){
			int j = n / (n / i);
			f[n] += (n / i) * (j - i + 1);
			i = j;
		}
	}
}	
int main(){
	int n,m,T;
	init();
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		ll ans = 0;
		for(int i=1;i<=min(n,m);i++){
			int j = min(n / (n / i),m / (m / i));
			ans += 1ll * (sum[j] - sum[i-1]) * f[n / i] * f[m / i];
			i = j;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1003ms, 内存消耗: 2524K, 提交时间: 2020-05-04 17:31:39

#include<bits/stdc++.h>
using namespace std;
#define ll long long  

const int N=5e4+100;

int p[N],mo[N],sum[N],tot=0;
ll s[N]; 
bool vis[N]; 
void init()
{
	mo[1]=1,sum[1]=1; 
	for(int i=2;i<N;i++)
	{
		if(vis[i]==0)
		{
			mo[i]=-1;
			p[++tot]=i;
		}
		for(int j=1;j<=tot&&i*p[j]<N;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				mo[i*p[j]]=0;
				break;
			}
			mo[i*p[j]]=-mo[i];
		}
		sum[i]=sum[i-1]+mo[i];
	}
	for(int i=1;i<N;i++)
	{
		ll ans=0;
		for(int j=1,r=1;j<=i;j=r+1)
		{
			r=i/(i/j);
			ans+=(r-j+1)*(i/j);
		}
		s[i]=ans;
	}
}

int main()
{
	init();
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		if(n>m) swap(n,m);
		
		ll ans=0;
		for(int i=1,r=1;i<=n;i=r+1)
		{
			r=min(n/(n/i),m/(m/i));
			ans+=(sum[r]-sum[i-1])*s[n/i]*s[m/i]; 
		}
		cout<<ans<<endl;
	} 
}