题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1492
题意:丑数(humble number)是一种素因子只有2、3、5、7组成的数字。给一个丑数,问它有多少因数。
题解:
求形如 <nobr> xy </nobr> 的因数个数
首先将 <nobr> xy </nobr> 唯一分解可以得到
<nobr> xy=∏i=1kpei×yi </nobr>
对于每一个因子 <nobr> pi </nobr> 可以取的个数为 <nobr> [0,ei×y] </nobr> 共 <nobr> ei×y−1 </nobr> 个
所以因子总数为
<nobr> S=∏i=1k(ei×y+1) </nobr>
对于这道题只需要把因数2.3.5.7的个数算出来+1相乘即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL n;
LL ans;
int calc(int x)
{
int tmp=0;
while(n%x==0) n/=x,tmp++;
ans*=tmp+1;
}
int main()
{
int tmp;
while(scanf("%lld",&n)&&n)
{
ans=1;
calc(2);calc(3);calc(5);calc(7);
printf("%lld\n",ans);
}
return 0;
}