求一个数组中每个数的约数有多少个

//如果分解每个数的因数 再找数组里出现过的数显然不好做
// 可以用埃氏筛的思想 枚举每个数作为因数 每个数的倍数累加这个因数出现的次数即可
//时间复杂度O(nlogn)
#include <iostream>
using namespace std;
const int N=1e6+10;
int cnt[N],a[N],mp[N],s[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++)
    {   
        for(int j=i;j<N;j+=i)
        {
            s[j]+=cnt[i];
        }
    }
    for(int i=1;i<=n;i++) cout<<s[a[i]]-1<<"\n";
}