UVa : 10083 - Division

問題概要

int型の範囲に収まる正の数、t, a, bが入力される。
(t^a - 1)/(t^b -1)という式に関して、以下のどれに当てはまるか答えよ。

• 答えが、100桁より短い整数になる
• それ以外の答えになる（100桁以上であったり、小数であったりする場合）

解法

一つ一つ無駄なパターンをつぶしていきましょう。

• tが1の場合
  • ゼロ除算が発生するため、答えは100桁より短い整数ではない
• aとbが一致する場合
  • tがどんな値であれ、必ず答えは1になる
• aをbで割り切れない
  • 答えが小数になる
• ( (a-b) × log10(t) )が99より大きくなる
  • 答えが100桁以上の数になる
• それ以外の場合
  • 答えは、100桁より短い整数になる
  • 単純にBigIntegerで計算していい
  • 何故なら、100桁より短くなる整数を満たすためには、aやbは大きくても100程度にしかならないから。普通にBigIntegerのpowとか使ってよし

プログラム

import java.util.*;
import java.math.BigInteger;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    while(sc.hasNextInt()){
      int t = sc.nextInt();
      int a = sc.nextInt();
      int b = sc.nextInt();

      System.out.printf("(%d^%d-1)/(%d^%d-1) ", t, a, t, b);

      // divide by 0
      if(t == 1){
        System.out.println("is not an integer with less than 100 digits.");
        continue;
      }

      // is not integer
      if(a % b != 0){
        System.out.println("is not an integer with less than 100 digits.");
        continue;
      }

      // is one
      if(a == b){
        System.out.println("1");
        continue;
      }

      // not less than 100 digits
      if((a - b) * Math.log10(t) > 99.0){
        System.out.println("is not an integer with less than 100 digits.");
        continue;
      }

      // calc
      BigInteger t_bi = new BigInteger(Integer.toString(t));
      BigInteger one = BigInteger.ONE;
      BigInteger calc =
        t_bi.pow(a).subtract(one).divide(t_bi.pow(b).subtract(one));

      if(calc.toString().length() >= 100){
        System.out.println("is not an integer with less than 100 digits.");
      }
      else{
        System.out.println(calc);
      }
    }
  }
}