P10390 [蓝桥杯 2024 省 A] 因数计数题解

· · 题解

已经给你了一个前置问题，求满足 a_i|a_j 的有序对 (i,j) 数，那么显然可以通过这个来容斥。

我的方法可能不是最简单的，如有更简单的方法欢迎爆破（

对于有序四元组 (i,j,k,l) ，先计算出满足 i\neq k\land j\neq l 的数量，然后分别排除掉满足 i=j，k=l，i=l，j=k 的四元组数量。（这里后两者其实是一样的）

对于 i=j ，固定了因数，直接找两个数字满足其都为 a_i 的倍数即可。

对于 k=l ，固定了倍数，直接找两个因数即可。

对于 i=l 或 j=k，固定了处在中间的数字，分别找一个因数和一个倍数即可。

注意上述三个情况都仍需要满足所找的数字与固定的数字不是同一个数字（数值可以相同），但不需要保证找的两个数字不同。

都可以通过与解决前置问题类似的方法求解。

然后再加上多减掉的部分。其总共有六种，但其中有四种的贡献都是零。因为在限制了 i\neq k\land j\neq l 的前提下不可能同时有三个数是同一个数字。

那么剩下的两种就是 i=j\land k=l 与 i=l\land j=k 。

前者数量其实就是前置问题的数量，对于后者需要简单分析一下，发现其等价于这四个数的数值相同。

那么就是选两个不同的数字且数值相同的方案数（选择数字有序，即选第 1，3 个数字与选 3，1 个数字算两种方案）。

没有下一层容斥了，因为后面的贡献都是零，原因与前面贡献为零的原因相同。

给出代码。

code

const int N=1e5+5;

int t[N],s[N];//分别是桶和因数个数

signed main(){
    signed n=read();
    for(int i=1;i<=n;i++)
        t[read()]++;
    int ans=0;
    int w=1e5;
    for(int i=1;i<=w;i++){
        if(t[i]==0)
            continue;
        ans+=t[i]*(t[i]-1);
        for(int j=i*2;j<=w;j+=i)
            ans+=t[i]*t[j];
    }ans*=ans+1;//加一是提前将第一个贡献加上，后面就不用再算一遍了
    for(int i=1;i<=w;i++){//i=j
        if(t[i]==0)
            continue;
        int sum=t[i]-1;
        for(int j=i*2;j<=w;j+=i)
            sum+=t[j];
        ans-=t[i]*sum*sum;
    }
    for(int i=1;i<=w;i++){//k=l
        if(t[i]==0)
            continue;
        s[i]+=t[i]-1;
        ans-=t[i]*s[i]*s[i];
        for(int j=i*2;j<=w;j+=i)
            s[j]+=t[i];
    }//print(ans),pc('\n');

    for(int i=1;i<=w;i++){//i=l||k=j
        if(t[i]==0)
            continue;
        int sum=t[i]-1;
        for(int j=i*2;j<=w;j+=i)
            sum+=t[j];
        ans-=t[i]*s[i]*sum*2;//这里乘二是同时计算两种
    }//print(ans),pc('\n');

    for(int i=1;i<=w;i++)
        if(t[i]>=2)
            ans+=t[i]*(t[i]-1);//第二个贡献，有序地选两个相同的数字的方案数
    print(ans),pc('\n');
    return 0;
}