好题23333
首先大力化柿子得到我们只需要筛这个玩意
\[F(x)=\sum\limits_{i|x} f(i) \mu(x/i)\]
考虑这玩意咋求？
不会弃了
然后就去颓题解
一开始想用组合数表示，后来发现消了消全变成0了？？
后来发现是我有个地方没考虑到
首先先考虑\(f(i)\)只有三种取值即\(F(x)\)和\(F(x)-1\)还有i=1的时候的0
同时\(\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)\)的时候
\[ ans_1= \sum\limits_{i|x\&\&f(i)==f(x)-1} (f(x)-1) \mu(x/i)\]
当\(f(i)=f(x)-1\)的时候
\[ ans_2= \sum\limits_{i|x\&\&f(i)==f(x)} f(x) \mu(x/i)\]
把两块加起来会得到
\[ ans= f(x) \sum\limits_{i|x} \mu(x/i) - \sum\limits_{i|x\&\&f(i)==f(x)-1} \mu(x/i) \]
以前和charm推过一个柿子:
\[\sum\limits_{i=0}^n (-1)^i C_n^{i}=[n==0]\]
具体证明的话i为奇数的时候显然，偶数的时候用杨辉三角搞一搞就好了。
它还有一个美妙的解释:任意非空集合的子集中大小为奇数和为偶数的一样。
然后我们看到前面那一部分就来劲了，这不就是把集合分成奇偶两部分奇加偶减嘛！！！！
所以
\[ ans=-\sum\limits_{i|x\&\&f(i)==f(x)-1} \mu(x/i) \]
然后当f(i)=f(x)-1的时候先把S集合塞到\(\mu\)里，T集合又是奇加偶减，又和上面一样了。
不一样的是上面的集合大小不能为0，这个可以为0，所以F并不全是0
可以写出一个简单的柿子(分情况讨论)来
如果S集合大小不等于全集 \(F(x)=0\)
不然的话如果全集大小是奇数 \(F(x)=1\)
不然就是 \(F(x)=-1\)
线筛无从下手的时候考虑化简形式
完结撒花
#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\n",calc(n,m));
}
return 0;
}原文：https://www.cnblogs.com/hzoi-kx/p/12115913.html