http://www.bnuoj.com/problem_show.php?pid=1026&tdsourcetag=s_pcqq_aiomsg

約數(shù)的個數(shù)

如果一個整數(shù)a能夠整除整數(shù)b，那么a叫做b的約數(shù)。
現(xiàn)在有N(1 <= N <= 100,000)個整數(shù)，對于其中的每一個數(shù)，請找出它在其余N - 1個整數(shù)中有多少個約數(shù)。

Input

輸入數(shù)據(jù)的第一行是一個整數(shù)N，以下N行每行有一個正整數(shù)，每個都不會超過1,000,000。

Output

按輸入順序輸出每個整數(shù)在其余N - 1個整數(shù)中的約數(shù)的個數(shù)，每個整數(shù)一行，總共輸出N行。

Sample Input

5
2
1
2
3
4

Sample Output

2
0
2
1
3

Source

第七屆北京師范大學(xué)程序設(shè)計(jì)競賽熱身賽第三場

Author

LiuLibo

數(shù)據(jù)不大，開個1e6的桶，統(tǒng)計(jì)每個數(shù)出現(xiàn)的次數(shù)，然后枚舉每個數(shù)的因子就好了。
然而枚舉時稍微用到了點(diǎn)常識吧，枚舉n的因子數(shù)，只需要枚舉到$sqrt n$，比如a是n的一個因子，那么$n/a$也是n的因子，枚舉到$sqrt n$就可一全覆蓋了。
可以結(jié)合此題加深理解：https://www.cnblogs.com/rmy020718/p/9602460.html

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
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
",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
",ans-1);
    }
//    fclose(stdin);fclose(stdout);
}

總結(jié)

以上是生活随笔為你收集整理的约数的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。