Hillan and the girl —— 莫比乌斯对两个累加的优化

本文主要是介绍Hillan and the girl —— 莫比乌斯对两个累加的优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
“WTF! While everyone has his girl(gay) friend, I only have my keyboard!” Tired of watching others’ affair, Hillan burst into scream, which made him decide not to hold it back.
“All right, I am giving you a question. If you answer correctly, I will be your girl friend.” After listening to Hillan, Girl replied, “What is the value of ∑ni=1∑mj=1f(i,j), where f(i,j)=0 if gcd(i,j) is a square number and f(i,j)=1 if gcd(i,j) is not a square number(gcd(i,j) means the greatest common divisor of x and y)?”
But Hillan didn’t have enough Intelligence Quotient to give the right answer. So he turn to you for help.

Input
The first line contains an integer T(1≤T≤10,000)——The number of the test cases.
For each test case, the only line contains two integers n,m(1≤n,m≤10,000,000) with a white space separated.

Output
For each test case, the only line contains a integer that is the answer.

Sample Input
2
1 2333333
10 10

Sample Output
0
33

Hint

In the first test case, obviously $f\left(i,j\right)$ always equals to 0, because $i$ always equals to 1 and $\gcd\left(i,j\right)$ is always a square number(always equals to 1).

这个有两个玩意，所以它构造出来就是
$\displaystyle\sum_{sqrt(k)=1}^{n} f(k)=$ $\displaystyle\sum_{k|p}^{} g(p)(p<=N)$
然后用莫比乌斯反演就可以得出我们要求的是
$\displaystyle\sum_{k=1}^{sqrt(n)}$ $\displaystyle\sum_{k|p}^{} μ(p/k)*f(p)$
而f(p)是在n,m中gcd=p的倍数所有数量，那么就等于
$\displaystyle\sum_{k=1}^{sqrt(n)}$ $\displaystyle\sum_{k|p}^{} μ(p/k)*(n/p)*(m/p)$
因为 $μ(p/k)$ 我们是可以预处理出来的，所以需要变换一下式子
$\displaystyle\sum_{p=1}^{n}(n/p)*(m/p)$ $\displaystyle\sum_{k|p}^{} μ(p/k)$
n/p和m/p可以通过整数分块加速

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define ll long long
int n,m;
const int maxn=1e7+5;
int nprime[maxn],prime[maxn],cnt,mu[maxn],sum[maxn];
void init()
{cnt=0;mu[1]=1;for(int i=2;i<maxn;i++){if(!nprime[i]){prime[++cnt]=i;mu[i]=-1;}for(int j=1;j<=cnt&&prime[j]*i<maxn;j++){nprime[prime[j]*i]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}mu[i*prime[j]]=-mu[i];}}for(int i=1;i<=sqrt(maxn)+eps;i++)for(int j=i*i;j<maxn;j+=i*i)sum[j]+=mu[j/i/i];for(int i=2;i<maxn;i++)sum[i]+=sum[i-1];
}
int main()
{int t;scanf("%d",&t);init();while(t--){scanf("%d%d",&n,&m);ll ans=0;int ne;if(n>m)swap(n,m);for(int i=1;i<=n;i=ne+1){int l=n/i,r=m/i;ne=min(n/l,m/r);ans+=(ll)(sum[ne]-sum[i-1])*l*r;}printf("%lld\n",(ll)n*m-ans);}return 0;
}