首页 > 专题系列 > Java解POJ > POJ 3307 Smart Sister [解题报告] Java
2013
11-12

POJ 3307 Smart Sister [解题报告] Java

Smart Sister

问题描述 :

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 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.

输出:

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.

样例输入:

4
10
1
40
11

样例输出:

10
1
80
12

解题代码:

//* @author 
import java.util.*;
public class Main{
  public static void main(String args[]){
  
    int k,n;
    Scanner in=new Scanner(System.in);
    k=in.nextInt();
    init();
    while(k-->0){
        n=in.nextInt();
       System.out.printf("%d\n",s[n]);
    }
   
   }

  static int MAX=80000;
  static long s[]=new long[MAX];       //用于存储结果,升序
  static long d2[]=new long[MAX];     //存储所有含有质因子2且符合条件的数
  static long d3[]=new long[MAX];     //存储所有含有质因子3且符合条件的数
  static long d5[]=new long[MAX];
  static long d7[]=new long[MAX];

  public static void init(){
    int i;
    int pos2,pos3,pos5,pos7;
    long 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;
    }
  }
}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。