自动搬运

查看原文

来自洛谷，原作者为

	LZH_LOVE_ZRG **

搬运于2025-08-24 22:30:37，当前版本为作者最后更新于2021-04-13 19:37:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

这里介绍几种 $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;
}

更新日志：

• 2021/4/13 更正了时间复杂度的计算；
• 2021/4/14 增加了第 $2$ 种解题方法；
• 2021/4/17 感谢 houzhiyuan 大佬的批评指正，更改了第 $2$ 种方法的计算。