题目4
标题：第几个幸运数
到x星球旅行的游客都被发给一个整数，作为游客编号。
x星的国王有个怪癖，他只喜欢数字3,5和7。
国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。
我们来看前10个幸运数字是：
3 5 7 9 15 21 25 27 35 45
因而第11个幸运数字是：49
小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。
请你帮小明计算一下，59084709587505是第几个幸运数字。
需要提交的是一个整数，请不要填写任何多余内容。
解题思路：用一个队列装幸运数,从3，5，7出发，依次将队首乘3，5，7的结果加入队尾（注意判重）,直到出现目标59084709587505.
程序代码如下：
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
long long q[10000];int mul[3]={3,5,7};
int main()
{
memset(q,sizeof(q),0);
q[0]=3;q[1]=5;q[2]=7;
int front=0;int rear=3;
while(front<rear)
{
for(int i=0;i<3;i++)
{
if(q[front]*mul[i]>59084709587505)continue;//大于59084709587505的排在后面的不入队列
long long t=q[front]*mul[i];
bool exist=0;
for(int j=rear-1;j>=0;j--)if(q[j]==t){exist=1;break;}//判断t是否已经在队列中
if(!exist)
{
q[rear]=t;rear++;//将t入队
if(t==59084709587505)//此时队尾元素已经是59084709587505,但还存在front到rear之间的元素和3,5,7相乘的结果小于59084709587505的可能
{
for(int k=front;k<rear-1;k++)//以上<59084709587505的可能情况，都应加入队列中
{
for(int i=0;i<3;i++)
{
long long t=q[k]*mul[i];
if(t<59084709587505)
{
bool exist=0;
for(int j=rear-1;j>=0;j--)if(q[j]==t){exist=1;break;}//判断t是否已经在队列中
if(!exist)
{
q[rear]=t;rear++;
}
}
}
}
sort(q,q+rear);//对3到59084709587505的幸运数进行排序
int pos=rear-1;
while(q[pos]!=59084709587505)pos--;//查找排序后的59084709587505所在的下标序号
cout<<pos+1<<endl;return 0;
}
}
}
front++;
}
return 0;
}
运行结果:1905