HDU - The number of divisors(约数) about Humble Numbers

时间:2022-06-21 08:58:48

Description

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.

Input

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. 

Output

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

Sample Input

4
12
0

Sample Output

3
6 ---------------------------------------------------------------我是分割线^_^----------------------------------------------------------------- 以后遇到英文题还是多解释一下吧,也是为了自己以后看的时候能更有效率,不然真的题目要看老半天= =。 题目的意思是寻找丑数的约数的个数一共有多少个,不包括自己,所谓丑数,就是约数只包含2,3,5,7(当然
默认的1已经包含进来了,因为除了0之外任何数都有一个约数为1嘛!)
这几个数的数,大概懂了题意之后,应该要想到丑数就是依靠着四个数建立起来的,就是这样:设2,3,5,7的
指数分别为a, b, c, d,则题目给定一个数n,就会有2^a * 3^b * 5^c * 7^d = n, 然后就可以知道了,这个n是由a个2,
b个3,c个5以及d个7乘出来的,接下来就可以组合出n的所有因数了,2最少有0个,最多有a个,同理,3,5,7也
一样,这样a个2,b个3,c个5以及d个7共有a*b*c*d种组合方式,这也就是n的所有因数的个数啦!
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
using namespace std; #define Int __int64 int main()
{
//freopen("input.txt", "r", stdin);
Int n;
while (scanf("%I64d", &n), n)
{
Int num[4] = {2, 3, 5, 7};
int ans[4] = {1, 1, 1, 1};//由在算的时候没有把0个2,0个3,0个5或者0个7的情况计算进去,所以一开始就加上
for (int i = 0; i < n; i++)
{
while (n != 1 && n % num[i] == 0)//算出2,3,5,7的个数
{
ans[i]++;
n /= num[i];
}
}
printf("%d\n", ans[0] * ans[1] * ans[2] * ans[3]);
}
return 0;
}