题目链接
思路
如果直接用暴力解法,逐个判断其他的数是不是它的约数,这样时间复杂度是O(n2),数据规模是105,会超时
假设A1是A2的约数的话,那么A2就是A1的倍数,因此可以做这么一个处理,当判定某个数Ak时,我们可以把这个数字的倍数Am全部加1
,含义是,Am的约数个数又多了1
。
但又考虑到可能会有很多个Ak的值是相同的,所以类似于计数排序的思想,先统计Ak出现的次数,然后再做上面的操作会方便一些
统计a[i]出现的次数:
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
cnt[i]!=0,即有某个Ak出现了,把Ak的倍数j
加上Ak出现的次数,即j
的约数个数又多了cnt[Ak]个
for(int i = 1; i < N; i++) {
if(!cnt[i]) continue;
//i其实就是Ak,j就是i的倍数
for(int j = i; j < N; j += i) {
res[j] += cnt[i];
}
}
最后,要在所有数中求Ak约数个数,res[Ak]就是Ak约数的个数(包括Ak自己)。可以想象,假设Ak=4,它在所有数中有两个约数A1=A2=2,经过上述操作后,res[4]的值应该是3,所以Ak的约数个数是res[Ak]−1=3−1=2
总结
约数和倍数其实是一对好基友,当求约数的时间复杂度过大时,不妨从它倍数的角度来考虑解决问题
代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10, M = 1e5 + 10;
int cnt[N], a[M], res[N];
int n;
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
for(int i = 1; i < N; i++) {
if(!cnt[i]) continue;
for(int j = i; j < N; j += i) {
res[j] += cnt[i];
}
}
for(int i = 0; i < n; i++) printf("%d\n", res[a[i]] - 1);
return 0;
}
写的很清楚
orz
为啥cnt数组改成 map or unordered_map就TLE啊 有没有大佬教教~
假设你写的没问题,那应该是以下原因导致:
1.map一次插入O(logn)而非O(1)
2.unordered_map一次插入容易被卡成O(n)
3.STL常数大,被卡常了
我的思路 TLE了 复杂度是nlg(max(a[i])) 最大约10^8
枚举每个a[i] 算其约数出现的次数,题主的方法很巧妙!
题主的方法更像打表
感觉复杂度也不低
for(int i = 1; i <= n; i ++ ) for(int j = i; j <= n; j += i) {}
其实这样的代码循环时间复杂度是 O(nlogn)
他这个for循环的第二层运行的次数是一个调和级数n + n/2 + n/3 + n/4 +.....1 可以证明时间复杂度是lnN级别的
%%%%%%%
%%%%%%%
好基友好评。