首页 > 专题系列 > Java解POJ > POJ 1152 An Easy Problem! [解题报告] Java
2013
11-09

POJ 1152 An Easy Problem! [解题报告] Java

An Easy Problem!

问题描述 :

Have you heard the fact “The base of every normal number system is 10″ ? Of course, I am not talking about number systems like Stern Brockot Number System. This problem has nothing to do with this fact but may have some similarity.

You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1). You will have to print the smallest possible value for N. The range for N is 2 <= N <= 62 and the digit symbols for 62 based number is (0..9 and A..Z and a..z). Similarly, the digit symbols for 61 based number system is (0..9 and A..Z and a..y) and so on.

输入:

Each line in the input will contain an integer (as defined in mathematics) number of any integer base (2..62). You will have to determine what is the smallest possible base of that number for the given conditions. No invalid number will be given as input. The largest size of the input file will be 32KB.

输出:

If number with such condition is not possible output the line “such number is impossible!” For each line of input there will be only a single line of output. The output will always be in decimal number system.

样例输入:

3
5
A

样例输出:

4
6
11

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
	
	static int get_base(char c){
		if(c>='0'&&c<='9')
			return c-'0'+0;
		if(c>='A' && c<='Z')
			return c-'A'+ 10;
		if(c>='a' && c<='z')
			return c-'a' + 36;
		return -1;
	}
	
public static void main(String[]args) throws Exception{
		
 int ans,i;
 String str;
 Scanner cin = new Scanner(System.in);
 //Scanner cin = new Scanner(new FileInputStream("input.txt"));
 while(cin.hasNext()){
	str = cin.next();
	for(ans=2;ans<=62;++ans){
		if(can(str,ans))
			break;
	}
	if(ans>62) System.out.println("such number is impossible!");
	else System.out.println(ans);
  }
}

 static boolean can(String str,int cnt){
  int i,sum=0;
  for(i=0;i< str.length();++i){
	if(get_base(str.charAt(i))>=cnt) return false;
	sum*=cnt;
	sum+=get_base(str.charAt(i));
	sum%=(cnt-1);
  }
  if(sum==0) return true;
  return false;
 }

 static int Max(int a,int b){
	return a>b?a:b;
 }
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。