結果
問題 | No.219 巨大数の概算 |
ユーザー | uafr_cs |
提出日時 | 2015-08-31 03:00:37 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,951 bytes |
コンパイル時間 | 2,912 ms |
コンパイル使用メモリ | 90,692 KB |
実行使用メモリ | 78,276 KB |
最終ジャッジ日時 | 2024-07-18 12:29:52 |
合計ジャッジ時間 | 43,391 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 5 TLE * 46 |
ソースコード
import java.math.BigDecimal; import java.math.BigInteger; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.Scanner; import java.util.Set; public class Main { public static class Value { long val, zero; public Value(long val, long zero){ //System.out.println(val); this.val = val; this.zero = zero; } public Value(long val){ this(val, 0); } public Value(Value v){ this(v.val, v.zero); } public static Value mul(Value a, Value b){ long zero = a.zero + b.zero; BigInteger value = BigInteger.valueOf(a.val).multiply(BigInteger.valueOf(b.val)); while(value.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0){ // 18桁 zero += value.toString().length() - 18; value = new BigInteger(value.toString().substring(0, 18)); } return new Value(value.longValue(), zero); } public String toString(){ String str = Long.toString(this.val); //System.out.println(str); return str.charAt(0) + " " + (str.length() == 1 ? "0" : str.charAt(1)) + " " + (this.zero + Math.max(0, str.length() - 1)) ; } } public static Value pow(Value A, long B){ if(B == 1){ return new Value(A); } if(B % 2 != 0){ return Value.mul(A, pow(A, B - 1)); } //System.out.println("A = " + A); //System.out.println("B = " + B); final Value ret = pow(A, B / 2); //System.out.println("RET = " + ret); return Value.mul(ret, ret); } public static BigDecimal pow(BigDecimal A, long B){ if(B == 1){ return A; } if(B % 2 != 0){ return A.multiply(pow(A, B - 1)); } final BigDecimal ret = pow(A, B / 2); return ret.multiply(ret); } public static void main(String[] args){ Scanner sc = new Scanner(System.in); final int N = sc.nextInt(); for(int tt = 0; tt < N; tt++){ final long A = sc.nextLong(); final long B = sc.nextLong(); System.out.println(pow(new Value(A), B)); } } }