首页 > ACM题库 > HDU-杭电 > hdu 2447 K-dimension number-最小生成树-[解题报告]C++
2014
01-26

hdu 2447 K-dimension number-最小生成树-[解题报告]C++

K-dimension number

问题描述 :

What a nice day! The sky is blue, and the sea is calm. It is a day that is suitable for marine navigation training. A training ship of a Naval Training School sails out from the naval port and arrives at a sea area. The navigation instructor is not only an expert in navigation but also an amateur mathematician. The instructor gives the practice assignment as soon as the first student stands at the position of the navigator: First, navigates 1 nautical mile to the east, and then 2 nautical miles to the south, finally 4 nautical miles to the west, and stops at a certain place. The first student accomplishes the task successfully. Then the second student takes the place, and the instructor gives him a new practice assignment: Firstly, navigates 1 nautical mile to the east, then 2 nautical miles to the south, and then 3 nautical miles to the west, finally 3 nautical miles to the north, and stops at a fixed place. Just like this, the students drive the training ship to accomplish the assignment one by one. There is a student who is interested in numbers and taking records. He writes down the first sequence 1, 2, and 4 as soon as the first student accepts the assignment. Later, he writes down the second sequence1, 2, 3, and 6 when the second student accepts the assignment. As a mathematic lover, the student always connects the numbers to some mathematic problems. When he writes down the first sequence, 1, 2, and 4, he figures out that every number in the sequence is the divisors of 4, and 4 is also the last number in the sequence. When he writes down the second sequence1, 2, 3 and 6, he also figures out that every number in the sequence is the divisors of 6, and 6 is also the last number in the sequence. After all the students have finished the assignment, the student looks at the record and comes to the conclusion followed: There is one thing in common for the assignments that the instructor has given to the students, that is, take the direction turning point as the gap, and the sailing distance in all directions form a sequence, every number in the sequence is the divisor of the last one.

The marine navigation training finishes. On the way back, the students have a good time, singing, talking, laughing, and appreciating the sea scenery. The student shows the instructor the records and tells him his findings. The instructor laughs and says to the student, “Well done! You like taking records and thinking, and then finding out something from it. It is a good habit, and also a scientific habit.” The instructor then continues, “Just like science does not have limit, the scientific questions do not have limit, either. The question we have just discussed will not end, and we can also pose new questions.”

The following is the new question the instructor raises:

First, we give a new definition: For a positive integer, if it has K different divisors, then it is called a K- dimension number.
For instance, the positive integer 4 has three divisors, 1, 2and 4, so 4 is a 3- dimension number. The positive integer 6 has four divisors, 1, 2, 3and 6, so 6 is a 4- dimension number.
Now a question is posed: how to work out the nth K-dimension number? (n<10000,Kmax<=100,here Kmax is the greatest prime divisor of K).And you can assume if K is a k-dimension number, it doesn’t exceed 3-dimension.

For example, if it is required to work out the second 3-dimension number, that is to say when n=2, K=3, then the answer is 9. Because 4 is the first 3-dimension number, and 9 has three common divisors 1, 3 and 9. Therefore, 9 is the second 3-dimension number.

The student thinks: if n and K are small enough, we can work out easily. Otherwise, we have to turn to the computer for n and K are too big to deal with.

He begins to think it over on the ship.

输入:

There are several test cases. Each case takes up a line, contains two positive integers; they are n and K respectively. Input is terminated by the end of the file.

输出:

There are several test cases. Each case takes up a line, contains two positive integers; they are n and K respectively. Input is terminated by the end of the file.

样例输入:

1 3
1 4

样例输出:

4
6

用Java写的。主要是为了保存代码···因为这次写的里面有排序,数组,类型转换,自定义的比较函数,堆,set等等。

import java.math.*;
import java.io.*;
import java.util.Scanner;
import java.io.File;
import java.*;
import java.io.*;
import java.util.*;

public class Main {

public static boolean IsPrime[] = new boolean [1 << 20];
    public static ArrayList<Long> Prime = new ArrayList();
   
public class Pair implements Comparable<Pair> {
   public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + a;
    result = prime * result + b;
    return result;
   }
   public boolean equals(Object obj) {
    if (this == obj)
     return true;
    if (obj == null)
     return false;
    if (getClass() != obj.getClass())
     return false;
    Pair other = (Pair) obj;
    if (a != other.a)
     return false;
    if (b != other.b)
     return false;
    return true;
   }
   public int a, b;
   public Pair(int x, int y) {
    a = x; b = y;
   }
   public int compareTo(Pair o) {
    Long rt = Prime.get(a) * Prime.get(b) – Prime.get(o.a) * Prime.get(o.b);
    if(rt < 0L) return -1;
    else if(rt == 0L) return 0;
    else return 1;
   }
}

   
    public static void init() {
    Arrays.fill(IsPrime, true);
    for(int i = 2; i < 1 << 20; i++) if(IsPrime[i]) {
       Prime.add(new Long(i));
       for(int j = i << 1; j < 1 << 20; j += i) IsPrime[j] = false;
    }
    }
   
public static void main(String[] args) {
    init();
    Scanner sin = new Scanner(new BufferedInputStream(System.in));
    int N, K, L = Prime.size();
    while(sin.hasNextInt()) {
       N = sin.nextInt(); K = sin.nextInt();
       if(K == 1) { System.out.println(1); continue; }
       int cnt = 0;
       long factor[] = new long[2];
       for(int i = 0; i < L; i++) {
        while(K % Prime.get(i) == 0) { factor[cnt++] = Prime.get(i); K /= Prime.get(i); }
       }
       if(cnt == 1) {
        BigInteger res = BigInteger.valueOf(Prime.get(N – 1));
        res = res.pow((int)factor[0] – 1);
        System.out.println(res);
        continue;
       }
       –N;
       ArrayList<BigInteger> tmp = new ArrayList();
       PriorityQueue<Pair> p = new PriorityQueue<Pair>();
       HashSet used = new HashSet();
      
       Main x = new Main() ;
       used.add(x.new Pair(0, 1));
       p.add(x.new Pair(0, 1));
      
       while(tmp.size() <= N) {
        Pair tt = p.remove();
        tmp.add(BigInteger.valueOf(Prime.get(tt.a) * Prime.get(tt.b)));
        if(tt.b != tt.a + 1 && used.add(x.new Pair(tt.a + 1, tt.b))) p.add(x.new Pair(tt.a + 1, tt.b));
        if(used.add(x.new Pair(tt.a, tt.b + 1))) p.add(x.new Pair(tt.a, tt.b + 1));
       }
       for(int i = 0; i < N; i++) tmp.add(BigInteger.valueOf(Prime.get(i)).pow((int)factor[0] + 1));
      
       Collections.sort(tmp);
       System.out.println(tmp.get(N).pow((int)factor[0] – 1));
    }
    }
}

解题转自:http://hi.baidu.com/orubwhsxihbhosd/item/23abf78e5042985d840fabb4