题目链接：

题意：

　　给你n个数，问你除a[i]之外，有多少个数是a[i]的约数。

 

题解：

　　ans[i]表示这n个数中有多少个数是i的约数。

　　对于a[i]，它对它倍数的答案有贡献：ans[a[i]*k]++

 

　　为了提高效率，可以先合并相同的a[i]。

　　cnt[i]代表值为i的数字有多少个。

　　所以变为：ans[i*k]+=cnt[i]

 

　　枚举每个数的倍数的总复杂度为O(nlogn)（调和级数）。

 

　　最后输出ans[a[i]]-1就好啦（不算自己）。

 

AC Code:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX_N 100005 5 #define MAX_R 1000005 6  7 using namespace std; 8  9 int n;10 int a[MAX_N];11 int cnt[MAX_R];12 int ans[MAX_R];13 14 int main()15 {16     scanf("%d",&n);17     memset(cnt,0,sizeof(cnt));18     memset(ans,0,sizeof(ans));19     for(int i=1;i<=n;i++)20     {21         scanf("%d",&a[i]);22         cnt[a[i]]++;23     }24     for(int i=1;i