题解 P7517 【[省选联考 2021 B 卷] 数对】

· · 题解

这是一道比较良心的弱省签到题，考察考生的基本代码能力。

这里介绍几种 2 比较简单的方法：

Solution 1：

对于每一个数 a_i，我们可以用 \sqrt{a_i} 的时间来枚举出这个数所有的因数。

具体实现为：用一个循环 j 枚举，每对数分别为 j 与 a_i\div j。

我们用一个桶来存储每个数作为因数出现次数，

然后最后用一个循环来累加所有答案。

时间复杂度：O(\sum\limits_{i=1}^{i<=n} \sqrt{a_i}+n)。

代码：

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
const int N=5e5+10;
int read(){//没有多大用的快读
    int f=1,s=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-') f=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        s=s*10+x-'0';
        x=getchar();
    }
    return f*s;
}
int a[N],b[N];//b即为桶
int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        for(int j=1;j*j<=a[i];j++){
            if(a[i]%j!=0) continue;//关键判断
            int ans1=j,ans2=a[i]/j;
            b[ans1]++;
            if(ans1!=ans2)//特判
                b[ans2]++;
        }
    }
    ll ans=0;//爆int警告
    for(int i=1;i<=n;i++)
        ans+=(ll)b[a[i]]-1;//累加，减一是减去自己的贡献
    cout<<ans;
    return 0;
}

Solution 2

对于每一个 a_i，改为枚举其倍数并累加其贡献。

用桶记录每个数出现的次数，再用一个数 j 枚举 a_i 乘上的因数。

贡献的次数就是 b_i\times b_{i\times j}+b_i\times (b_i-1)，后者就是 a_i 是自己的倍数的情况。

时间复杂度：调和级数时间复杂度，即为 O(\max{a_i} \times \log{\max{a_i}})。

代码：

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
const int N=5e5+10;
int read(){
    int f=1,s=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-') f=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        s=s*10+x-'0';
        x=getchar();
    }
    return f*s;
}
int a[N],b[N];
int main(){
    int n=read();
    for(int i=1;i<=n;i++)
        b[read()]++;
    ll ans=0;
    for(int i=1;i<=N;i++){
        for(int j=2;i*j<=N;j++)
            ans+=b[i]*b[i*j];
        ans+=b[i]*(b[i]-1);
    }
    cout<<ans;
    return 0;
}

更新日志：