自动搬运

查看原文

来自洛谷，原作者为

	Fading AFO

搬运于2025-08-24 22:09:50，当前版本为作者最后更新于2019-05-05 19:34:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

数论毒瘤题

后面根本不会做了，什么求和套路都用光了。

所以还是自己容斥学的太差了。。。

不过这题简直就是多合一啊

讲讲我的心路历程：

做这道题之前请做一做$P2257$和$P1587$和$SP4168$

顺便安利一下我的题解

前面都是自己瞎推的，后面思路参考了楼上的大佬。

题意：

设一个函数$f(i)$，满足

$$\sum_{i|j}f(j)=\mu(i)$$

求$f(m)$

然后很显然的用莫比乌斯反演定理的第$2$种形式

复习一下前几天还说莫比乌斯反演定理没用

若

$$g(i)=\sum_{i|j}f(j)$$

则

$$f(i)=\sum_{i|j}g(j)\mu(\frac ji)$$

证明：

$$\sum_{i|j}g(j)\mu(\frac ji)=\sum_{i|j}\sum_{j|k}f(k)\mu(\frac ji) $$$$=\sum_{i|k}\sum_{\frac ji|\frac ki}f(k)\mu(\frac ji) $$

设$d=\frac ji$

$$=\sum_{i|k}f(k)\sum_{d|\frac ki}\mu(d)\ =\ \sum_{i|k}f(k)[\frac ki==1] $$$$=\sum_{i|k}f(k)[k==i]\ =f(k)$$

证完了。

---

所以我们用一用莫比乌斯反演定理就有

$$f(m)=\sum_{m|j}\mu(\frac jm)\mu(j)$$

套路去设$k=\frac jm$

$$=\sum_{k=1}^{\lfloor \frac nm\rfloor}\mu(k)\mu(km) $$

这就又用到了循环之美的套路了，不会的可以看一看我的小结中的第$3$条

$\mu(ij)=\mu(i)\mu(j)[gcd(i,j)==1]$

所以就可以拆掉了

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

这前面都是自己推的，然后后面我就懵逼了

怎么求这个式子

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

我想到了$SPOJ$那道题！

考虑没有$gcd$的情况

$$\sum_{i=1}^{n}\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac n{i^2}\rfloor $$

我们要求的就是$1$~$n$中不是完全平方数$(1$除外$)$倍数的数的个数。

然后根据枚举平方因子的倍数个数，然后容斥，且容斥系数为$\mu$，就得到了我们要的式子

不懂的可以看我的题解或者$Sooke$的题解。

其实现在就多了一个条件，这个数和$m$互质，于是我就去推式子了。

容斥容斥，搞不出来，样例没过。。。

然后就参考了$ywwywwyww$巨佬的题解！

我们容斥的不是$\lfloor\frac n{i^2}\rfloor$的个数吗？

它的意义是什么？不就是平方数的倍数个数吗？

只要这个平方数的倍数和$m$互质不就好了吗？？？

设$p=i^2j$就是这个平方数的个数

必须要有$gcd(p,m)=1$。

即$gcd(i^2j,m)=1$。

设$h(i)$表示$i^2$的倍数中与$m$互质的数的个数

所以我们现在要求的不就是

设$\lfloor \frac nm\rfloor=N$

$$\sum_{i=1}^{\sqrt{N}}\mu(i)h(i)\ \ ?$$

然后怎么求$h$?

我的思路和巨佬居然是类似的！惊喜！！！

我们分类讨论$i$和$m$的关系。

如果$gcd(i,m)!=1$，那么无论如何$gcd(p,m)$都不会等于$1$了，因为$p=i^2j$

所以$h(i)$直接等于$0$就可以了。

否则，

$$h(i)=\sum_{j=1}^{\lfloor\frac N{i^2}\rfloor}[gcd(i^2j,m)==1] $$$$\because gcd(i,m)==1$$ $$h(i)=\sum_{j=1}^{\lfloor\frac N{i^2}\rfloor}[gcd(j,m)==1] $$

这个继续用套路

$$=\sum_{j=1}^{\lfloor\frac N{i^2}\rfloor}\sum_{d|j,d|m}\mu(d)\ =\ \sum_{d|m}\sum_{j=1}^{\lfloor\frac {\lfloor\frac N{i^2}\rfloor}d\rfloor}\mu(d) $$$$=\ \sum_{d|m}\mu(d)\lfloor\frac {\lfloor\frac N{i^2}\rfloor}d\rfloor $$

枚举$m$的约数就可以快速计算了。

然后这道题就做完了，设$m$有$\alpha$个约数，时间复杂度就是$O(T\alpha\sqrt N)$

对了不要忘记外层还有一个$\mu(m)!!!$

看不懂的还可以私信问我。

具体实现非常恶心？

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,T,p[100001],d[100001],arfa,tot,vis[100001],mu[100001],MU[100001];
inline void init(ll nx){
    mu[1]=1;
    for (register int i=2;i<=nx;i++){
        if (!vis[i]) p[++tot]=i,mu[i]=-1;
        for (register int j=1;j<=tot&&(ll)i*p[j]<=nx;j++){
        	if (1LL*i*p[j]>nx) continue;
            vis[1LL*i*p[j]]=1;
            if((i%p[j])==0){
                mu[1LL*i*p[j]]=0;
                break;
            }
            mu[1LL*i*p[j]]=-mu[i];
        }
    }
}
ll Mu(ll a){//求单个数的莫比乌斯函数
    if (a<=35001) return mu[a];
    ll x=a,cnt=0;
    for (ll j=2;j*j<=a;j++){
        if (x%j==0){
        	ll now=0;
            while (x%j==0) now++,x/=j;
            if (now>1) return 0;
            cnt++;
        }
    }
    if (x!=1) cnt++;
    return (cnt&1)?-1:1;
}
inline ll h(ll I){
    if (__gcd(I,m)!=1) return 0;
    ll ans=0;
    for (int i=1;i<=arfa;i++){
        ans+=MU[i]*(n/m/(I*I)/d[i]);
    }
    return ans;
}
int main(){
    init(35005);
    cin>>T;
    while (T--){
        cin>>n>>m;
        arfa=0;
        for (int i=1;i*i<=m;i++){
            if (m%i==0) d[++arfa]=m/i,d[++arfa]=i;//枚举因数
        }
        if (d[arfa]==d[arfa-1]) d[arfa--]=0;
        for (int i=1;i<=arfa;i++){
            MU[i]=Mu(d[i]);//预处理每一个因数的莫比乌斯函数
        } 
        ll ans=0;
        for (register int i=1;i*i<=n/m;i++){
            ans+=mu[i]*h(i);
        }
        printf("%lld\n",Mu(m)*ans);
    }
}