题解 P5348 【密码解锁】

· · 题解

数论毒瘤题

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

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

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

讲讲我的心路历程：

做这道题之前请做一做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);
    }
}