「一本通 6.2 练习 2」轻拍牛头

题意:给$ n(1 \le n \le 10^5) $个数,每个数小于$10^6$求每个数因数的个数.

如果暴力的话是$ O(n^2) $的. 每个数的倍数+1;这样就行算出每个数的因数了.
自己的1倍也要+1,这是为了统计相同的数字.最后答案减去1;

#include
using namespace std;
int n,a[100005],cnt[1000006];
int main(){
    scanf("%d",&n);
    int maxx=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        maxx=max(maxx,a[i]);
    }
    for(int i=1;i<=n;++i){
        for(int j=a[i];j<=maxx;j+=a[i])
        ++cnt[j];
    }
    for(int i=1;i<=n;++i)
    printf("%d\n",cnt[a[i]]-1);
    return 0;
    
}

但是这样做超时了,这个和埃筛的区别在于,埃筛没有重复的数字.如果某个数字重复了,比如说有n个1,那肯定会超时.所以要把相同的数放在一起.

#include
using namespace std;
int n,a[100005],cnt[1000006],ans[1000006];
int main(){
    scanf("%d",&n);
    int maxx=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        ++cnt[a[i]];
        maxx=max(maxx,a[i]);
        
    }
    for(int i=1;i<=maxx;++i)
    if(cnt[i]) 
    for(int j=i;j<=maxx;j+=i)
    ans[j]+=cnt[i];
    for(int i=1;i<=n;++i)
    printf("%d\n",ans[a[i]]-1);
    return 0;
    
}