好题23333
首先大力化柿子得到我们只需要筛这个玩意
考虑这玩意咋求？
不会弃了
然后就去颓题解
一开始想用组合数表示，后来发现消了消全变成0了？？
后来发现是我有个地方没考虑到
首先先考虑(f(i))只有三种取值即(f(x))和(f(x)-1) 还有i=1的时候的0
值得注意的是以下均没考虑i=1,因为当i=1且(mu(x)!=0)的时候x的所有质因子次数均为1
也就是此时的0包含在(f(x)-1)里
同时(mu(x/i))也很美妙，当x/i的某一个质因子>1的时候，它就谢比了。
首先把x的质因子分成两个集合S和T,其中S是次数最高的质因子，T是其他的。
所以考虑把数x劈成两部分，一部分给f,一部分给(mu)的过程。
如果把S集合全给了(mu)那么不管T集合怎么折腾，f(i)的值一定是f(x)-1
不然的话就是f(x)
那么当(f(i)=f(x)-1)的时候
当(f(i)=f(x))的时候
把两块加起来会得到
以前和charm推过一个柿子:
具体证明的话i为奇数的时候显然，偶数的时候用杨辉三角搞一搞就好了。
它还有一个美妙的解释:任意非空集合的子集中大小为奇数和为偶数的一样。
然后我们看到前面那一部分就来劲了，这不就是把集合分成奇偶两部分奇加偶减嘛！！！！
所以
然后当f(i)=f(x)-1的时候先把S集合塞到(mu)里，T集合又是奇加偶减，又和上面一样了。
不一样的是上面的集合大小不能为0，这个可以为0，所以F并不全是0
可以写出一个简单的柿子(分情况讨论)来
如果S集合大小不等于全集 (F(x)=0)
不然的话如果全集大小是奇数 (F(x)=1)
不然就是 (F(x)=-1)
线筛无从下手的时候考虑化简形式
完结撒花
ps:其实我上面在说垃圾话，其实可以视为是用了莫比乌斯函数的性质
即(sumlimits_{i|n} mu(i)=[n==1])和(sumlimits_{i=0}^{n}(-1)^i C_{n}^{i}=[n==0])把前一个柿子n的质因子种类数和后面柿子的n视为一个东西 两个是等价的！！！
妙啊 而且也可以把后面那个柿子看作((1-1)^n)。
#include<cstdio>
#include<iostream>
#define LL long long
#define reg register
using namespace std;
const int N=1e7,maxn=N+9;
int f[maxn],g[maxn],mu[maxn],p[maxn],cnt,low[maxn],sum[maxn],tt[maxn],mxcnt[maxn];
inline void pre() {
mu[1]=1;
for(reg int i=2;i<=N;++i) {
if(!low[i]) mu[i]=-1,p[++cnt]=i,low[i]=f[i]=g[i]=tt[i]=mxcnt[i]=1;
for(reg int j=1;j<=cnt&&p[j]*i<=N;++j) {
if(i%p[j]) {
f[i*p[j]]=f[i],low[i*p[j]]=1,mu[i*p[j]]=-mu[i],tt[i*p[j]]=tt[i]+1;
if(f[i]==1) mxcnt[i*p[j]]=mxcnt[i]+1;
else mxcnt[i*p[j]]=mxcnt[i];
}
else {
f[i*p[j]]=max(low[i]+1,f[i]),low[i*p[j]]=low[i]+1,mu[i*p[j]]=0,tt[i*p[j]]=tt[i];
if(low[i]+1==f[i]) mxcnt[i*p[j]]=mxcnt[i]+1;
else if(f[i]>low[i]+1) mxcnt[i*p[j]]=mxcnt[i];
else mxcnt[i*p[j]]=1;
break;
}
}
g[i]=mxcnt[i]==tt[i]?(tt[i]&1?1:-1):0;
}
for(reg int i=1;i<=N;++i) sum[i]+=sum[i-1]+g[i];
return ;
}
inline LL calc(int n,int m,LL ans=0) {
for(reg int l=1,lt=min(n,m);l<=lt;++l) {
int x=n/l,y=m/l,r=min(n/x,m/y);
ans+=1ll*(sum[r]-sum[l-1])*x*y;
l=r;
}
return ans;
}
int main() {
pre();
int T;scanf("%d",&T);
while(T--) {
int n,m;
scanf("%d%d",&n,&m);
printf("%lld
",calc(n,m));
}
return 0;
}