P10390 题解

KSCD_ · 2024-06-20 10:51:33 · 题解

思路

（是 @Iceturky 的思路，在此拜谢）

值域小，为了方便表示设值域 P={10}^5。先开桶 t_x 表示 x 出现的次数。同时预处理出每个数编号不相等的因数个数 s_x 和倍数个数 b_x，时间复杂度为调和级数 O(P\ln P)。

考虑先算出 i\ne j 且 a_i\mid a_j 的 (i,j) 数量 m，枚举较小数 x，得 m=\sum_{x=1}^{P}t_x\times b_x。

有了以上问题的答案，平方一下就是 a_i\mid a_k,a_j\mid a_l 且 i\ne k,j\ne l 的 (i,j,k,l) 组数，还需要容斥减去 i=j,i=l,k=j,k=l 的组数。

首先先减去满足一个条件的：

还需要加上满足两个条件的：

• 其他四种情况都会产生 i=k 或 j=l，与已经确定的条件 i\ne k,j\ne l 冲突，所以组数为 0。

之后满足三个或四个条件也会产生同样的冲突，组数均为 0，不用处理。

这样就做完了，但是由于 n^4 达到了 {10}^{20} 级别，开 __int128 才能确保通过。

代码

#include<iostream>
#define int __int128
using namespace std;
const int N=1e5+10;
const int P=1e5;
int read()
{
    int s=0,w=1;
    char ch; ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
void print(int x)
{
    if(x>=10) print(x/10);
    putchar(x%10+'0');
}
int n,ans,t[N],s[N],b[N];
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) t[read()]++;
    for(int i=1;i<=P;i++) if(t[i])
    {
        for(int j=i*2;j<=P;j+=i) if(t[j])
            b[i]+=t[j],s[j]+=t[i];
        b[i]+=t[i]-1,s[i]+=t[i]-1;
        ans+=t[i]*b[i];
    }
    ans*=(ans+1); //无限制和 i=k && j=l 
    for(int i=1;i<=P;i++) if(t[i])
    {
        ans-=t[i]*b[i]*b[i]; // i=j
        ans-=t[i]*s[i]*s[i]; // k=l
        ans-=2*t[i]*b[i]*s[i]; // i=l || j=k
        ans+=t[i]*(t[i]-1); // i=l && j=k 
    }
    print(ans);
    return 0;
}