首先题目给出一个定义,一个数具有productive property是指这个数是另一个数所有位上数字的乘积。如2是12各位上数字的乘积,80也是:80=2*2*2*5。
题目要求给出一个正整数i,求出按升序排列后第i个具有productive property的数是多少。题目保证结果不会大于10^18。
最直接的想法就是找出所有这样的数,然后排序,按i输出相应的数。
这里我走了一条弯路,一开始是想找出所有的数,这些数没有大于10的质因子,但这样就要打素数表,还要对一个数进行试除,时间复杂度比较高(从10试到10^18)。
其实反过来想,时间复杂度可以大大降低:这些数的因子只能是2,3,5,7,由这些因子所产生的合数数目肯定大大小于10^18。
简单计算一下可以知道:2^59<10^18, 3^37<10^18, 5^25<10^18, 7^21<10^18。因此只要产生59*37*25*21<=1146075个数就够了。
如何高效产生这些数呢?这里使用了类似DFS+剪枝的技术,设当前这个数为tmp, 则若tmp*c>10^18就不用再乘下去了,其中c是2,3,5,7其中某个数的幂次。具体见程序里的 init
#include <iostream>
#include <algorithm>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
__int64 b=1;
__int64 a[1146075];
__int64 f[4][60];
void init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
// i,j,k,l分别是2,3,5,7的幂次
int i,j,k,l,cnt=0;
// 预先计算阶乘
b=1;
for(i=1;i<=18;i++) b*=10;
f[0][0]=f[1][0]=f[2][0]=f[3][0]=1;
for(i=1;i<=59;i++) f[0][i]=f[0][i-1]*2;
for(i=1;i<=37;i++) f[1][i]=f[1][i-1]*3;
for(i=1;i<=25;i++) f[2][i]=f[2][i-1]*5;
for(i=1;i<=21;i++) f[3][i]=f[3][i-1]*7;
// 产生所有质因子在10以内的数
__int64 tmp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0;i<=59;i++)
{
tmp=f[0][i];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0;j<=37;j++)
{
if(tmp*f[1][j]>=b) break;
else tmp*=f[1][j];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(k=0;k<=25;k++)
{
if(tmp*f[2][k]>=b) break;
else tmp*=f[2][k];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(l=0;l<=21;l++)
{
if(tmp*f[3][l]>=b) break;
else a[cnt++]=tmp*f[3][l];
}
tmp/=f[2][k];
}
tmp/=f[1][j];
}
tmp/=f[0][i];
}
sort(a,a+cnt);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
init();
int t,i;
scanf("%d",&t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(t--)
{
scanf("%d",&i);
printf("%I64d\n",a[i-1]);
}
return 1;
}