下面给出部分分做法和满分做法
有一些奇妙的方法可以拿到同样多的分数，本蒟蒻只能介绍几种常见的做法
如果您想拿18分左右，需要了解：质因数分解
如果您想拿30分左右，需要了解：一种较快的筛法
如果您想拿70分左右，需要了解：莫比乌斯反演+杜教筛+整除分块+容斥
如果您想拿100分，需要了解：线性筛+杜教筛+莫比乌斯函数+狄利克雷卷积+推式子+微积分+整除分块
这时候如果您还想做这道题的话。。。
18分做法
首先N=1 时，就是求不超过 M的完全平方数有多少个，直接输出(lfloor sqrt{M} floor)就好啦。
将 a中的最大完全平方因子除去以后所得的数记为 A
将 b中的最大完全平方因子除去以后所得的数记为 B
因为ab是完全平方数，所以AB是完全平方数，因为A，B只含一次方的质因数，所以A=B
枚举a，由于 a/A是 a的约数中最大的完全平方数，可以枚举不超过a 的所有完全平方数求出 a的最大平方约数（或把a 分解质因数）来计算出A
b一定是A的完全平方数倍，A固定时b的取值一共有 (lfloor sqrt{M / A} floor)个。
时间复杂度：O((N⋅ $sqrt{N} $)
30分做法
枚举A，计算有多少组对应的有序数对(a,b)。
A只能取不包含平方因子的数，只需让 a/A，b/A为完全平方数，并且 (1 leq a leq N, 1 leq b leq M) 。
当 A确定时，a,b可以取的值的即分别不超过 (lfloor N / A floor) 和 (lfloor M / A floor) 的完全平方数，即分别有 (iglfloorsqrt{lfloor N / A floor}ig floor)和 (iglfloorsqrt{lfloor M / A floor}ig floor)种取值
A即不超过 (min(N,M))的不包含平方因子的数。可以用筛法求出来
把所有（大于1的）完全平方数的倍数筛掉，剩下的就是不包含平方因子的数。
时间复杂度是O( (min(N, M)))
然后枚举 A，将对应的 a和b 的数量乘起来（即 (iglfloorsqrt{lfloor N / d floor}ig floor imes iglfloorsqrt{lfloor M / d floor}ig floor)）计入答案。
时间复杂度： O((min(N, M))))。
大约70分的做法
不妨设 (N leq M)
考虑枚举数对 a和 b的最大公约数，设为d。则a/d与b/d 必须是互质的完全平方数，于是我们可以统计([1, lfloor sqrt{frac N d} floor])与([1, lfloor sqrt{frac M d} floor])中互质数的对数。
答案就是 (sum _d sum _i ^ {lfloor sqrt{frac N d} floor} sum _j ^ {lfloor sqrt{frac M d} floor}[ gcd (i, j) = 1])
是一个经典的莫比乌斯反演问题；于是我们在(sqrt{N})范围线性筛，再对d分块处理。时间O（(sqrt{N}cdot 大常数)）
优秀的话可以拿到95分
（开始乱搞）
大约70分做法（懒得写那么多惹，有的地方默认M,N同级）
根据上文易知答案 =(sum_{x=1}^{min(N, M)} mu^2(x) cdot iglfloorsqrt{lfloor N / x floor}ig floor cdot iglfloorsqrt{lfloor M / x floor}ig floor)
根据容斥原理，(mu^2)的前缀和 $ sum_{x=1}^{n} mu^2(x) = sum_{i=1}^{lfloor sqrt{n} floor} mu(i) cdot lfloor frac{n}{i^2} floor $
你发现$lfloorfrac{n}{i^2} floor $可以整除分块
O(( ^{1/3}))的时间复杂度内计算
可以整除分块(iglfloorsqrt{lfloor N / x floor}ig floor cdot iglfloorsqrt{lfloor M / x floor}ig floor)
用线性筛预处理(sqrt{N}) 以内的(mu) 的前缀和，(mu^2)的前缀和
(iglfloorsqrt{lfloor N / x floor}ig floor)一共改变了 (O(N^{1/3}))次值，所以 (iglfloorsqrt{lfloor N / x floor} ig floor cdot iglfloorsqrt{lfloor M / x floor}ig floor) 一共改变了 (O(min(M^{1/3}+N^{1/3}, min(M,N)))) 次值
为什么呢？
张老师给出的证明：
如果(min(M^{1/3}+N^{1/3}, min(M,N)))大约是我们需要计算 (mu^2)的前缀和的次数。
如果计算 (mu^2)的前缀和的复杂度为 (O(N^{1/3}))
这个算法的时间复杂度约为(O(N^{1/3} cdot min(M^{1/3}+N^{1/3}, min(M+N)ig) ig))
感觉很虚，优化得和没有优化一样
仔细计算时间：
对(n=1) 到 (O(min(M^{1/3}+N^{1/3}, min(M+N))))计算 (sum_{x=1}^{n} mu^2(x))
时间复杂度约为 (Oleft(int_1^{min(M^{1/3},N)} x^{1/3} mathrm{d}x ight) = Oleft(min(M^{4/9}, N^{4/3}) ight))
然后对 $sqrt{M / n} = sqrt{M / N} (到) M^{1/3}
$ 计算 (sum_{x=1}^{n} mu^2(x))
时间复杂度为 (Oleft(int_{sqrt{M/N}}^{M^{1/3}} M^{1/3}x^{-2/3} mathrm{d}x ight) = Oleft(min(M^{4/9},M^{1/2}) - M^{1/2}N^{-1/6} ight))
所以，当 (max(N,M) > left(min(N,M)
ight)^3)
时，时间复杂度为 (Oleft(left(min(N,M)
ight)^{4/3}
ight))
而且因为一部分(mu^2)已经预处理了，所以实际的时间复杂度还会小一些
大约90分做法
（题解太长，我有点不想写了）
发现上一个的算法的问题在于空间
令线性筛预处理范围 (S < sqrt{N})
记 (summu(n) = sum_{x=1}^{n} mu(x), summu^2(n) = sum_{x=1}^{n} mu^2(x))
我们需要计算这些$ mu^2$的前缀和： (summu^2(N))
(summu^2left(leftlfloor frac{M}{left(lfloorsqrt{M / N} floor + 1 ight)^2} ight floor ight),)
$ summu^2left(leftlfloor frac{M}{left(lfloorsqrt{M / N} floor + 2 ight)^2} ight floor ight), $
(dots)
和形如 (summu^2(lfloor frac{N}{dots} floor)) 的前缀和
计算 (mu^2)的前缀和的过程： (summu^2(n) = sum_{i=1}^{lfloor sqrt{n} floor} mu(i) cdot lfloor frac{n}{i^2} floor)
所以在计算 (summu^2(n))时需要求 (summu(lfloor sqrt{n} floor), summu(lfloor sqrt{n / 2} floor), summu(lfloor sqrt{n / 3} floor), dots)
计算(mu)的前缀和的过程（由狄利克雷卷积可求出）：(summu(n) = 1 - sum_{i=2}^{n} summu(lfloor n / i floor))
如果一次性求出所有满足 $lfloor n / i floor > S (的) summu(lfloor n / i floor)$(i为正整数），所需时间复杂度为 (Oleft(int_{1}^{n / S} sqrt{n / x} mathrm{d}x ight) = O(n cdot S^{-1/2}))
杜教筛 (O(n^{2/3}))的时间复杂度就是 (O(n cdot S^{-1/2} + S))
根据上述信息，所有要计算的(mu)的前缀和：
(mathrm{for}_{i=lfloor sqrt{M/N} floor}^{lfloor sqrt{M}/S floor} mathrm{for}_{j=1}^{lfloor M / (i^2S^2) floor} summu(lfloor frac{sqrt{M}}{i sqrt{j}} floor))
交换一下循环顺序，可以发现只需计算所有满足 (lfloor frac{M/j}{i} floor > S) 的 (summu(lfloor frac{M/j}{i} floor))
时间复杂度为 (Oleft(int_1^{M / S^2} sqrt{M / x} cdot S^{-1/2} mathrm{d}x ight) = O(M cdot S^{-3/2}))
这样我们可以取 (S = left(max(N,M) ight)^{3/7} < 9000000)
做到 (Oleft( left(max(N,M)
ight)^{3/7}
ight))
的总时间复杂度。
得分： 95~100 分。
意思是分析了这么久，优化来优化去，如果写的丑的话，还是没有100分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20000031;
bool vis[N];
int p[N /10],mu[N];
ll mu2[N];
int maxn=0;
void init(){
mu[1]=1;
for(int i=2,tot=0;i<=maxn;i++){
if(!vis[i]) p[tot++]=i,mu[i]=-1;
for(int j=0;j<tot&&i*p[j]<=maxn;j++){
vis[i*p[j]]=1;
if(i%p[j]) mu[i*p[j]]=-mu[i];
else{
mu[i*p[j]] = 0;
break;
}
}
}
for(int i=1;i<=maxn;++i) mu2[i]=mu2[i-1]+(mu[i]!=0),mu[i]+=mu[i-1];
}
ll m,n;
inline ll squ(ll x){return x*x;}
map<ll,ll> qq;
ll g(ll x){
if(x<=maxn) return mu[x];
auto it=qq.find(x);
if(it!=qq.end()) return it->second;
ll ans=1;
for (ll i=2,j=0;i<=x;i=j+1) ans-=g(x/i)*((j=x/(x/i))-i+1);
return qq[x]=ans;
}
ll f(ll x){
if(x<=maxn) return mu2[x];
ll ans=0,i=1,t=0,a=0,b=0;
for(;i*i*i<=x;++i)t=x/squ(i),ans+=t*((a=mu[i])-b),b=a;
for(ans-=(t=x/squ(i))*b;t;--t)ans+=g(sqrt(x/t));
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
if (n>m) swap(n,m);
maxn=min((ll)(pow(m,3/7.0)),n);
init();
ll ans=0,x=0,y=0,a=0,b=0;
for(ll i=1,j=0;i<=n;i=j+1) j=min(n/squ(x=sqrt(n/i)),m/squ(y=sqrt(m/i))),ans+=x*y*((a=f(j))-b),b=a;
printf("%lld
",ans);
}