# Poj Solution 2847

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

//* @author:alpc12
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

String num;
boolean ok;

void DFS(int dep, String b) {
if(b.length() == num.length())
return;
int i, j;
for(i = 0; i <= 9; ++i) {
BigInteger now = new BigInteger(""+i+b);
String nows = now.multiply(now).multiply(now).toString();
if(nows.length() >= num.length() && nows.substring(nows.length()-num.length()).equals(num)) {
ok = true;
System.out.println(now);
return;
}
if(nows.length() > dep) {
int all = Math.min(dep, num.length()-1);
for(j = 0; j <= all; ++j) {
if(nows.charAt(nows.length()-1-j) != num.charAt(num.length()-1-j))
break;
}
if(j > all) {
DFS(dep+1, ""+i+b);
if(ok) return;
}
}
}
}

void run() {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
for (int i = 0; i < n; ++i) {
num = cin.next();
ok = false;
DFS(0, "");
if(!ok) while(true);
}
}

public static void main(String[] args) {
new Main().run();

}

}

```
This entry was posted in poj. Bookmark the permalink.