题目分析

$\mu(m)=\sum_{m|d} F(d)$

$F(m)=\sum_{m|d} \mu(d) \mu(\frac{m}{d})$

$=\mu(m) \sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\mu(i)^2 [gcd(i,m)==1]$

$=\mu(m) \sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\mu(i)^2 \sum_{t|i,t|m} \mu(t)$

$=\mu(m)\sum_{t|m} \mu(t) \sum_{t|i}^{\lfloor \frac{n}{m} \rfloor} \mu(i)^2$

将 $m$分解质因数，然后暴力枚举 $t$。接下来就是最后那个 $\sum$的问题。

显然 $\mu(i)^2$不是 0 就是 1。

利用容斥完成，先设它们全是１，贡献是范围以内的 $t$的倍数的个数。然后减去有因子 $2^2$的数的贡献（这些数同样是 $t$的倍数），减去有因子 $3^2$的贡献，加上有因子 $6^2$的贡献（多算了）……以此类推。

这个式子可以利用莫比乌斯函数容斥，记 $\lfloor \frac{n}{m} \rfloor=k$，直接写为 $\sum_{i=1}^{\sqrt{k}} mu(i)(k$以内既是 $t$倍数又是 $i^2$倍数的数的个数 $）$

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
typedef long long LL;
const int N=100000;
LL n,m;int T,js,tot,pri[35],is[N+5],p[N+5],mu[N+5];

void prework() {
    int tot=0;mu[1]=1;
    for(RI i=2;i<=N;++i) {
        if(!is[i]) p[++tot]=i,mu[i]=-1;
        for(RI j=1;j<=tot&&p[j]*i<=N;++j) {
            is[p[j]*i]=1;
            if(i%p[j]==0) break;
            else mu[p[j]*i]=-mu[i];
        }
    }
}
LL dfs(int x,int now,int nowmu) {
    if(x==js+1) {
        LL re=0;
        for(RI i=1;i*i<=n/m;++i) {
            LL tmp=1LL*i*i/__gcd(i*i,now)*now;
            re+=n/m/tmp*mu[i];
        }
        return re*nowmu;
    }
    return dfs(x+1,now,nowmu)+dfs(x+1,now*pri[x],-nowmu);
}
LL work() {
    int km=m;js=0;
    for(RI i=2;i*i<=km;++i) if(km%i==0) {
        int c=0;
        while(km%i==0) km/=i,++c;
        if(c>1) return 0;
        pri[++js]=i;
    }
    if(km!=1) pri[++js]=km;
    return dfs(1,1,1)*((js&1)?-1:1);
}

int main()
{
    scanf("%d",&T),prework();
    while(T--) scanf("%lld%lld",&n,&m),printf("%lld\n",work());
    return 0;
}