题解
大力筛倍数即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using namespace std;
typedef long long ll;
int n,a[100005],cnt[1000005]={0},ans[1000005]={0};
void init(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]),cnt[a[i]]++;
}
void solve(){
for(int i=1;i<=1000000;i++){
if(cnt[i]){
for(int j=i;j<=1000000;j+=i)
ans[j]+=cnt[i];
}
}
for(int i=0;i<n;i++)
printf("%d\n",ans[a[i]]-1);
}
int main(){
init();
solve();
return 0;
}