BZOJ 3309: DZY Loves Math

BZOJ 3309: DZY Loves Math

题目

解法

显然，这是一道莫比乌斯反演。
因为a,b顺序与答案无关，所以我们强制(a<b)
然后乱搞一波就会得到

[ans=sum_{D=1}^{a}frac{a}{D}frac{b}{D}sum_{d|D}f(d)mu(frac{D}{d}) ]

前面的套路大家都清楚，重要的是后面的那一部分怎么求。

我们令(g(x)=sum_{d|x}f(d)mu(frac{x}{d}))
将(x),(d)分解质因数得到
(x=P_1^{a_1}P_2^{a_2}...P_n^{a_n})
(d=P_1^{b_1}P_2^{b_2}...P_n^{b_n})
因为莫比乌斯函数(mu)的原因，我们的只有对于(forall i都有a_i-b_ileq 1)时(f)对答案才有贡献。
也就是说我们要从这(n)个不同的质因子中任选一部分使次数-1，得到(d),求(f(d))
然后若(exists a_i<a),那么不论这一位选与不选(f(d)最终答案都与这一位无关),而对于莫比乌斯函数(mu)来说，这就是(1和-1)的区别，所以此时(g(x)=0)，只有当所有(a_i=a)时，有一种特殊情况就是每个数都被选时会使(f(d)=a-1),不能与其他情况合并为0,所以它对答案的贡献是-1,再乘上莫比乌斯函数(mu),最终(g(x)=(-1)^{n+1})

综上所述
假设(x=P_1^{a_1}P_2^{a_2}...P_n^{a_n})
若对于(forall i,j)都有(a_i=a_j)
那么(g(x))=(-1)^{n+1}
否则(g(x)=0)

这样(g(x)就可以通过线性筛筛出来)
而$$ans=sum_{D=1}^{a}frac{a}{D}frac{b}{D}g(D)$$
所以答案就很好求了。

完整代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int _=1e7+20,M=1e7+1;
int prime[_],f[_],low[_],num[_],isprime[_],s;
void pre(){
    for(int i=2;i<=M;++i){
        if(!isprime[i])low[i]=num[i]=f[i]=1,prime[++s]=i;
        for(int j=1;j<=s&&i*prime[j]<=M;++j){
            int k=i*prime[j];
            isprime[k]=1;
            if(i%prime[j]){
                low[k]=1;num[k]=i;
                f[k]= low[k]==low[i]?-f[i]:0;
            }
            else {
                low[k]=low[i]+1;num[k]=num[i];
                if(num[k]==1)f[k]=1;
                else f[k]=low[k]==low[num[k]]?-f[num[k]]:0;
                break;
            }
        }
    }
    for(int i=1;i<=M;++i)
        f[i]+=f[i-1];
}
int main(){
    pre();
    int T;
    cin>>T;
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        ll ans=0;
        for(int l=1,r;l<=n;l=r+1){
            r=min(m/(m/l),n/(n/l));
            ans+=1ll*(n/l)*(m/l)*(f[r]-f[l-1]);
        }
        printf("%lld
",ans);
    }
}