约数的个数

如果一个整数a能够整除整数b，那么a叫做b的约数。

现在有N(1 <= N <= 100,000)个整数，对于其中的每一个数，请找出它在其余N - 1个整数中有多少个约数。

 

Input

输入数据的第一行是一个整数N，以下N行每行有一个正整数，每个都不会超过1,000,000。

 

Output

按输入顺序输出每个整数在其余N - 1个整数中的约数的个数，每个整数一行，总共输出N行。

 

Sample Input

521234

Sample Output

20213

Source

Author

LiuLibo

 

数据不大，开个1e6的桶，统计每个数出现的次数，然后枚举每个数的因子就好了。

然而枚举时稍微用到了点常识吧，枚举n的因子数，只需要枚举到$\sqrt n$，比如a是n的一个因子，那么$n/a$也是n的因子，枚举到$\sqrt n$就可一全覆盖了。

可以结合此题加深理解：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int read(){    int sum=0,fg=1; char c=getchar();    while(c<'0'||c>'9'){ if(c=='-')fg=-1;c=getchar(); }    while(c>='0'&&c<='9'){ sum=sum*10+c-'0';c=getchar(); }    return sum*fg;}int n,ans,a[100006],sum[1000006],vis[1000006];int main(){//    freopen("A.in","r",stdin);//    freopen("A.out","w",stdout);    n=read();    for(int i=1;i<=n;i++)a[i]=read(),sum[a[i]]++;    for(int i=1;i<=n;i++)    {        if(vis[a[i]]>0)        {            printf("%d\n",vis[a[i]]);            continue;        }        ans=0;        int p=sqrt(a[i]);        for(int j=1;j<=p;j++)        {            if(a[i]%j==0)            {                if(a[i]/j==j)ans+=sum[j];                else ans+=sum[j],ans+=sum[a[i]/j];            }        }        vis[a[i]]=ans-1;        printf("%d\n",ans-1);    }//    fclose(stdin);fclose(stdout);}