题目链接:https://www.luogu.org/problemnew/show/P2257
题解:莫比乌斯反演,这个不是简单的入门莫比乌斯反演,需要数学,好难~~~
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int maxn = 10000000 + 10;
int mu[maxn], vis[maxn], prim[maxn]; //莫比乌斯需要的数组,可以求出素数以及个数
int cnt = 0; //有多少个素数
void get_mu(int n)
{
mu[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!vis[i]) { prim[++cnt] = i; mu[i] = -1; }
for (int j = 1; j <= cnt && prim[j] * i <= n; j++)
{
vis[prim[j] * i] = 1;
if (i%prim[j] == 0)break;
else mu[i*prim[j]] = -mu[i];
}
}
}
int sum[maxn],f[maxn]; //用来求前缀和与后面的预处理的结果
void solve()
{
for (int i = 1; i <= cnt; i++)
for (int j = 1; prim[i] * j <= 10000000; j++)
f[j*prim[i]] += mu[j];
for (int i = 1; i <= 10000000; i++)
sum[i] = sum[i - 1] + f[i];
}
int main()
{
get_mu(10000000);
solve();
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
if (n > m)
{
n = n ^ m;
m = n ^ m;
n = n ^ m;
}
ll ans = 0;
for (int l = 1, r; l <= n; l=r+1)
{
r = min(n / (n / l), m / (m / l));
ans += (ll)(sum[r] - sum[l - 1])*(ll)(n / l)*(ll)(m / l);//这里不能加上(r-l+1),因为每次加上的值不一样,需要用前缀和处理
}
cout << ans << endl;
}
return 0;
}