首页 > ACM题库 > 九度OJ > 九度-1087 约数的个数[数论]
2014
03-13

九度-1087 约数的个数[数论]

题目来源:2011年清华大学计算机研究生机试真题

题目描述:
输入n个整数,依次输出每个数的约数的个数
输入:
输入的第一行为N,即数组的个数(N<=1000)
接下来的1行包括N个整数,其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
输出:
可能有多组输入数据,对于每组输入数据,
输出N行,其中每一行对应上面的一个数的约数的个数。
样例输入:
5
1 3 4 6 12
样例输出:
1
2
3
4
6

 

此题解法比较多。

1) 可以直接暴力求解,用类似找素数的方法。循环到 sqrt(n) 逐个判断.

#include <iostream>
#include <cmath>

using namespace std;

int main(void)
{
        int n;
        while (cin >> n)
        {
                int num;
                while (n--)
                {
                        int count = 0;
                        cin >> num;

                        int i;
                        for (i = 1; i < sqrt((double)num); i++)
                        {
                                if (num % i == 0)
                                {
                                        count += 2;
                                }
                        }
                        if (i * i == num)
                        {
                                count++;
                        }
                        cout << count << endl;
                }
        }
        return 0;
}

2) 用约数个数定理。百科:http://baike.baidu.com/view/1780622.htm

用约数个数定理做的,只贴出功能函数,主函数里面调用该函数即可。

unsigned int factors(unsigned int n)
{
        unsigned int i = 2, k = 0, m = n, count = 1;
        while(m != 1)
        {
                for(; i <= m; i ++)
                        if(m % i == 0)
                        {
                                k = 1;
                                while(m % i == 0)
                                {
                                        k ++;
                                        m /= i;
                                }
                                count *= k;
                        }
        }
        return count;
}

不用进行素数判定,for循环找到的 i 一定是素数。

自认为该算法应该算比较简洁明了的。
经验证,平均性能比穷举法(O(n))的速度快很多,10^12左右的合数都能瞬间出结果,穷举法要好几秒(不过对于素数,该算法就退化为穷举法了,也就是说最坏情况下时间复杂度为O(n))。


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n