注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

POJ 3307 Smart Sister  

2009-05-01 21:06:34|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Smart Sister
Time Limit: 2000MS  Memory Limit: 65536K
Total Submissions: 1948  Accepted: 756

Description

Yesterday, Kamran was working on a report, which he must submit to his boss next Saturday. He became tired and went out of his working room to take a nap. After some minutes, her sister, Kamelia, who is a first year university student, came to the room and found the report. She thought, "How many large positive integers in a document. I hate these large numbers, they make me see nightmares! I should represent them in a more compact way". At first, she devised an ambiguous way to represent a number. She computed the product of digits of a number to find a new number and repeated this process again and again until she reached a one digit number (For example, 972 was transformed to 126 and then to 12 and finally to 2).

But she simply understood that this process is not reversible and tried to find another way (Since she loves Kamran too much, she did not want to destroy his efforts!). Suddenly, she noticed an interesting  property in all the numbers of the report and called it productivity property in her mind. By her definition, a number with productivity property is a number that can be obtained by multiplying the digits of some other number (for instance, 126, 12, and 2 has productivity property, because they can be obtained from 972, 126, and 12 respectively). She thought, "Wow, I found it. If a number x in the report is the ith number in the increasing sequence of positive integers having productivity property, I will replace it by i". She replaced all numbers of the report, put a note for Kamran describing what she did with the numbers of his report and went to her friend's home in a blink of an eye!!!

It is not hard to imagine, how loudly Kamran screamed when he saw the report and the note from
Kamelia! In addition, he wondered how she did this! He thought "Again this naughty smart sister". Now, Kamran needs your help to find his original report numbers.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case includes a positive integer i which is the number written by Kamran's sister in the report. Please note than input includes thousands of test cases.

Output

For each test case, your program must output the original number x that was converted to the given i.
Please note that it is guaranteed that the output number is less than 1018.

Sample Input

4
10
1
40
11
Sample Output

10
1
80
12
Source

Amirkabir University of Technology Local Contest 2006

 

题目大意:如果一个数可以通过其他数的各数字位相乘得到,则说这个数具有productivity property。要求求出第i个具有这种性质的数。

主要思想:

1.从题目的意思最容易想到的办法就是从10开始一直到10^18(1~9很明显符合条件),找出其中所有具有这种性质的数并存到一个数组中,然后只要将i作为数组小标就可以得到答案了。但是怎么判断这个数是否符合要求呢?如果说一个数具有题目所给的性质,那么这个数的质因子一定只能从2,3,5,7中选。显然如果含有其他的质因子,比如11,那么这个数肯定不能由其他数的各数字位相乘得到。但是因为需要遍历的范围太大,这种方法一定会超时。

2.这时候我们可以从另一个角度来分析这道题目,我们可以通过四个质因子来生成所有其他的数,然后将生成的数按序存在数组里就可以了。因为从1~9除了1,2,3,5,7外都可以通过这些数相乘得到,而大于9的数要是符合条件也一定能拆成几个一位数相乘,所以可以肯定通过2,3,5,7能生成所有符合条件的数。具体实现可以从s[1]=1开始乘以四个质因子,然后从中选出最小的,并将这个数给s[2],然后再将s[2]乘以四个质因子,重复上面的步骤。这里用四个数组分别存放含有质因子2,3,5,7的数,这几个数组中一定存在相同的数,所以可以通过代码中的四个while循环去掉不需要的数。

代码如下:

#include<iostream>
#define MAX 80000
using namespace std;
__int64 s[MAX];       //用于存储结果,升序
__int64 d2[MAX];     //存储所有含有质因子2且符合条件的数
__int64 d3[MAX];     //存储所有含有质因子3且符合条件的数
__int64 d5[MAX];
__int64 d7[MAX];
void init(){
    int i;
    int pos2,pos3,pos5,pos7;
    __int64 a,b;
    s[1]=1;
    pos2=pos3=pos5=pos7=1;
    for(i=1;i<MAX-1;i++){

        d2[i]=s[i]*2;
        d3[i]=s[i]*3;
        d5[i]=s[i]*5;
        d7[i]=s[i]*7;

        while(d2[pos2]<=s[i])pos2++;     //如果这个数小于s[i],那么它一定已经在s[i]中,可以去掉。
        while(d3[pos3]<=s[i])pos3++;     //显然s[i]是从四个数组中从小到大选出来的,
        while(d5[pos5]<=s[i])pos5++;     //所以上面的做法一定是正确的
        while(d7[pos7]<=s[i])pos7++;
        a=d2[pos2]<d3[pos3]?d2[pos2]:d3[pos3];
        b=d5[pos5]<d7[pos7]?d5[pos5]:d7[pos7];
        s[i+1]=a<b?a:b;
    }
}
int main(){
    int k,n;
    scanf("%d",&k);
    init();
    while(k--){
        scanf("%d",&n);
        printf("%I64d\n",s[n]);
    }
    return 0;
}

后记:从这道题可以学会从不同的角度去考虑一个问题,可以得到完全不一样的效果。

问题:这里还留下了一个问题,当我用long long型的时候就WA掉了,不知道是为什么?

  评论这张
 
阅读(372)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017