首页 > ACM题库 > HDU-杭电 > HDU 1492 The number of divisors(约数) about Humble Numbers-数论应用-[解题报告] C++
2013
12-11

HDU 1492 The number of divisors(约数) about Humble Numbers-数论应用-[解题报告] C++

The number of divisors(约数) about Humble Numbers

问题描述 :

A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … shows the first 20 humble numbers.

Now given a humble number, please write a program to calculate the number of divisors about this humble number.For examle, 4 is a humble,and it have 3 divisors(1,2,4);12 have 6 divisors.

输入:

The input consists of multiple test cases. Each test case consists of one humble number n,and n is in the range of 64-bits signed integer. Input is terminated by a value of zero for n.

输出:

For each test case, output its divisor number, one line per case.

样例输入:

4
12
0

样例输出:

3
6

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1492

题意:丑数(humble number)是一种素因子只有2、3、5、7组成的数字。给一个丑数,问它有多少因数。

mark:基础数论。因为只有2、3、5、7四种素因子,因此只要求出幂次,加1后乘起来就好了。注意要用long long。

代码:

# include <stdio.h>


long long div(long long x, int b)
{
    int rtn = 0 ;
    while (x%b==0)
    {
        x /= b ;
        rtn ++ ;
    }
    return rtn ;
}


int main ()
{
    long long n, mul ; 
    while (~scanf ("%I64d", &n),n)
    {
        mul = 1 ;
        mul *= (div(n,2)+1) ;
        mul *= (div(n,3)+1) ;
        mul *= (div(n,5)+1) ;
        mul *= (div(n,7)+1) ;
        printf ("%I64d\n", mul) ;
    }
    return 0 ;
}

解题报告转自:http://www.cnblogs.com/lzsz1212/archive/2012/04/11/2441660.html


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  4. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法