算法1
(暴力枚举) O(N2)
求出每个数的因数
算法2
O(NlogN)
反过来考虑,对于每个数d,在1~N中以d为约数的数就是d的倍数,d,d2,d3…,N/d*d。因此可以从小到大枚举每个约数,将约数统计到这个约数的倍数对应的数上去。
两层循环,第一层枚举每个因数
第二层扫因数的倍数
时间复杂度
参考文献
C++ 代码
#include "iostream"
using namespace std;
const int N = 1e6+10;
int a[N],cnt[N],s[N];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> a[i],cnt[a[i]]++; //记录因数出现的次数
for(int i = 1; i < N; ++i)
for(int j = i; j < N; j+=i)
if(cnt[i]) s[j] += cnt[i]; //如果这个数有,就统计
for(int i = 0; i < n; ++i) cout << s[a[i]] - 1 << endl; //题目要求不包含自己的因数
return 0;
}