POJ 2847 - The Cubic End

http://poj.org/problem?id=2847

概要

末尾の桁が 1, 3, 7, 9 であるような N 桁の数が与えられる． このような数は，ある値を3乗した末尾 N 桁がその数になるような値が必ず存在することが知られているので，その値を答える．

制約

解法

下の桁から順に埋めていくだけ．

最大で ( 10^10 )^3 くらいを計算することになるので，BigInteger を使うと楽．

 1 import java.util.*;
 2 import java.io.*;
 3 import java.math.*;
 4 
 5 public class Main {
 6   public static void main(String[] args) {
 7     Scanner cin = new Scanner(System.in);
 8     int T = cin.nextInt();
 9     while (T-- > 0) {
10       String s = cin.next();
11       char[] cs = s.toCharArray();
12       BigInteger ans = BigInteger.ZERO;
13       BigInteger e = BigInteger.ONE;
14       for (int i = 0; i < cs.length; i++) {
15         for (int j = 0; j < 10; j++) {
16           BigInteger t = BigInteger.valueOf(j).multiply(e).add(ans);
17           BigInteger n = t.pow(3);
18           String sn = n.toString();
19           if (i < sn.length() && sn.charAt(sn.length()-1-i) == cs[cs.length-1-i]) {
20             ans = t;
21           }
22         }
23         e = e.multiply(BigInteger.TEN);
24       }
25       System.out.println(ans);
26     }
27   }
28 }
poj/2847.java