0022:洛谷P2926_Patting Heads S()

链接: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 }
————————

链接: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 }