链接：https://www.luogu.com.cn/problem/P2926
暴力会超时，只有47分。
于是我们要用类似于质数筛的算法去求。
将数据存到桶里，然后如果桶里有数就枚举它的倍数，如果它的倍数也在桶里，用另一个数组将它加上。
上代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 int arr[1000001],brr[1000001],crr[1000001];
4 int main(){
5 int n;
6 cin>>n;
7 for(int i=1;i<=n;i++){
8 cin>>arr[i];
9 brr[arr[i]]++;//存入桶
10 }
11 for(int i=1;i<=1000001;i++){
12 if(!brr[i]){//如果没有，直接退
13 continue;
14 }
15 for(int j=1;j<=1000001/i;j++){//枚举倍数
16 if(brr[i*j]){
17 crr[i*j]+=brr[i];//c数组加上之前那个数的数量
18 }
19 if(i*j==i){
20 crr[i*j]--;//不能算自己
21 }
22 }
23 }
24 for(int i=1;i<=n;i++){
25 cout<<crr[arr[i]]<<endl;
26 }
27 }
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/279013.html