【テンプレート/約数】牛頭を軽く叩く

牛の頭を軽くたたく

        ，         ，          ．

    N    （   1   N）     。

   1    N     ，i      i−1    i+1      ，N      1      。

               ，           1   1000000      。

        i          ，        Ai   。

          ，          ，          ，                      ，       。

           ，              。

    N     A1,A2,…,AN，       Ai，               。

    
        N。

    N  ，         Ai。

    
  N  ，  i        i            。

    
1≤N≤105,
1≤Ai≤106
    ：
5
2
1
2
3
4
    ：
2
0
2
1
3

#include

using namespace std;
const int N=1000010;
int n;
int a[N],cnt[N],s[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&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++) printf("%d
",s[a[i]]-1);
    return 0;
}