「题解」P4466 [国家集训队]和与积

· · 题解

Description

给定 n，求满足 1\le a<b \le n 且 a+b \mid ab 的 (a,b) 个数。

# Solution 小清新反演题。 考虑提取 $d=\gcd(a,b)$，令 $a \leftarrow \dfrac{a}{d}, b \leftarrow \dfrac{b}{d}$，此时条件转化为 - $a<b

不妨枚举 a，可以发现答案即为

\sum_{a=1}^{\sqrt n}\sum_{b=a+1}^{\sqrt n} \left\lfloor\frac{\left\lfloor\frac{n}{b}\right\rfloor}{a+b}\right\rfloor [\gcd(a,b)=1]

这是因为，由于 ad<bd\le n，d 最大只能取到 \left\lfloor\dfrac{n}{b}\right\rfloor。同时 \left\lfloor\dfrac{\left\lfloor\frac{n}{b}\right\rfloor}{a+b}\right\rfloor 只有在 a,b \le \sqrt n 时才不为 0。

可以开始大力 Möbius 反演推式。

\begin{aligned}\sum_{a=1}^{\sqrt n}\sum_{b=a+1}^{\sqrt n} \left\lfloor\frac{\left\lfloor\frac{n}{b}\right\rfloor}{a+b}\right\rfloor [\gcd(a,b)=1]&=\sum_{a=1}^{\sqrt n}\sum_{b=a+1}^{\sqrt n} \left\lfloor\frac{\left\lfloor\frac{n}{b}\right\rfloor}{a+b}\right\rfloor \sum_{d \mid \gcd(a,b)} \mu(d)\\&= \sum_{d=1}^{\sqrt n} \mu(d) \sum_{a=1}^{\left\lfloor\frac{\sqrt n}{d}\right\rfloor}\sum_{b=a+1}^{\left\lfloor\frac{\sqrt n}{d}\right\rfloor} \left\lfloor\frac{\left\lfloor\frac{n}{bd^2}\right\rfloor}{a+b}\right\rfloor \\&= \sum_{d=1}^{\sqrt n} \mu(d) \sum_{b=1}^{\left\lfloor\frac{\sqrt n}{d}\right\rfloor}\sum_{a=1}^{b-1} \left\lfloor\frac{\left\lfloor\frac{n}{bd^2}\right\rfloor}{a+b}\right\rfloor \end{aligned}

显然 \left\lfloor\dfrac{n}{bd^2}\right\rfloor 是定值，那么对里面的部分整除分块即可。

不难发现时间复杂度即为

\sum_{i=1}^{\sqrt n}\sum_{j=1}^{\left\lfloor\frac{\sqrt n}{i}\right\rfloor} \sqrt{\left\lfloor\frac{n}{i^2j}\right\rfloor}

大力积分，可以得到 \mathcal O(n^{\frac{3}{4}})。

值得一提的是这题其实是有 \mathcal O(n^{\frac{2}{3}}) 做法的，只需要对 zhylj 神的题解中的 S(n) 整除分块就行了，因为 \left\lfloor\dfrac{n}{i^2}\right\rfloor 只有 \mathcal O(n^{\frac{1}{3}}) 种取值。不过太毒瘤了，时间复杂度也很难算……不想讲。我在 U 群提问后 @142857cs 和 @wkywkywky 等众神告诉了我这个复杂度的可行性。希望后人可以胜任这个工作，完成一篇严格 \mathcal O(n^{\frac{2}{3}}) 的题解。

Code

typedef long long LL;
const int N=46341,P=4793;

int n,tot,p[P],Mo[N];
LL Ans;
bitset<N> v;

void Mob(int n) {
    Mo[1]=1;
    for (int i=2;i<=n;i++) {
        if (v[i]==0)
            Mo[i]=-1,p[++tot]=i;
        for (int j=1;j<=tot && i*p[j]<=n;j++) {
            v[i*p[j]]=1;
            if (i%p[j]) Mo[i*p[j]]=-Mo[i];
            else {
                Mo[i*p[j]]=0;
                break;
            }
        }
    }
}

int Calc(int s,int x) {
    int Sum=0;
    for (int l=s+1,r;l<(s<<1);l=r+1) {
        if (!(x/l)) return Sum;
        r=min(x/(x/l),(s<<1)-1);
        Sum+=(r-l+1)*(x/l);
    }
    return Sum;
}

int main() {
    scanf("%d",&n);
    int m=sqrt(n);
    Mob(m);
    for (int i=1;i<=m;i++)
        if (Mo[i]) {
            for (int j=1;j<=m/i;j++)
                Ans+=Mo[i]*Calc(j,n/(i*i*j));
        }
    printf("%lld",Ans);
    return 0;
}