网站建设找seo综合查询 站长工具

 题意：求ai在n个数中，ai可以整除的数有多少个，不包括ai自己。

分析：暴力写需要n^2的时间复杂度，此时想一下预处理每个数的倍数，约数和倍数是有关系的，把每个数的倍数都加上1.

#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;
int s[N];
int cnt[N];
int a[N];int main()
{int n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];cnt[a[i]]++;}for(int i=1;i<N;i++)//这两重循环是O(nlogn)的{for(int j=i;j<N;j+=i){s[j]+=cnt[i];}}for(int i=1;i<=n;i++) cout<<s[a[i]]-1<<endl;return 0;    
}