ZJU PAT 1010 RadixITeye - 乐橙lc8

ZJU PAT 1010 RadixITeye

2019年02月26日10时43分54秒 | 作者: 向彤 | 标签: 本题,办法,运用 | 浏览: 1649

标题见:http://pat.zju.edu.cn/contests/pat-a-practise/1010

本题选用二分办法查找进制,留意因为我运用的办法是转换为十进制进行比较,所以C/C++中即便运用了long long 类型也可能会溢出,为便利起见,本题选用Java的BigInteger完成;或许能够考虑自己完成一个大数类。

import java.math.BigInteger;
import java.util.Scanner;
public class Main{
 private static BigInteger bs0 = new BigInteger("0");
 private static BigInteger bs1 = new BigInteger("1");
 private static BigInteger bs2 = new BigInteger("2");
 // Or you can use: Character.getNumericValue(c)
 private static int charToInt(char c) {
 return c = 9 ? (c - 0) : (c - a + 10);
 private static BigInteger getBigIntegerBased10(int val) {
 return new BigInteger(String.valueOf(val));
 private static BigInteger getNumber(String s, BigInteger radix) {
 BigInteger t = bs0;
 BigInteger p = bs1;
 char c;
 BigInteger temp;
 for (int i = s.length() - 1; i i) {
 c = s.charAt(i);
 temp = getBigIntegerBased10(charToInt(c));
 t = t.add(temp.multiply(p));
 p = p.multiply(radix);
 return t;
 private static void handle(String a, String b, int radix) {
 char c = b.charAt(0);
 BigInteger v1 = getNumber(a, getBigIntegerBased10(radix));
 if (b.length()  1) {
 int bv = charToInt(c);
 if (v1.intValue()  bv) {
 System.out.println(bv + 1);
 } else {
 System.out.println("Impossible");
 return;
 for (int i = 1; i b.length(); i++) {
 if (b.charAt(i) c)
 c = b.charAt(i);
 // Determine the lower bound of the radix
 BigInteger l = getBigIntegerBased10(charToInt(c) + 1);
 BigInteger r = v1;// Determine the upper bound of the radix
 // System.out.println(l + " : " + r);
 BigInteger m, v2;
 while (l.compareTo(r) = 0) {
 m = l.add(r).divide(bs2);
 v2 = getNumber(b, m);
 if (v1.equals(v2)) {
 System.out.println(m);
 return;
 } else if (v1.compareTo(v2) 0) {
 r = m.subtract(bs1);
 } else {
 l = m.add(bs1);
 System.out.println("Impossible");
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 String a = scanner.next();
 String b = scanner.next();
 int tag = scanner.nextInt();
 int radix = scanner.nextInt();
 if (tag  1)
 handle(a, b, radix);
 else
 handle(b, a, radix);

 

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表乐橙lc8立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章