### Find the largest 0 to 9 pandigital that can be formed by concatenating products题号：170 难度： 70 中英对照

Take the number 6 and multiply it by each of 1273 and 9854:

6 × 1273 = 7638
6 × 9854 = 59124

By concatenating these products we get the 1 to 9 pandigital 763859124. We will call 763859124 the "concatenated product of 6 and (1273,9854)". Notice too, that the concatenation of the input numbers, 612739854, is also 1 to 9 pandigital.

The same can be done for 0 to 9 pandigital numbers.

What is the largest 0 to 9 pandigital 10-digit concatenated product of an integer with two or more other integers, such that the concatenation of the input numbers is also a 0 to 9 pandigital 10-digit number?

### Code

public final class p170 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run() {
max=0;
dfs(0);
return ""+max;
}

static long max;
static int dig[]=new int[10];
static boolean vis[]=new boolean[10];
private static void dfs(int pos) {
if(max!=0) return;
if(pos<10){
for(int i=9;i>=(pos==0?1:0) && max==0;i--){
if(vis[i]) continue;
vis[i]=true;
dig[pos]=i;
dfs(pos+1);
vis[i]=false;
}
}else{
solve();
}
}
static void solve(){
long num=0;
for(int i=0;i<10;i++){
num*=10;
num+=dig[i];
}
for(long k=1;k<=num/k;k++) if(num%k==0){
for(int i=1;i<10;i++){
long A=0,B=0;
for(int j=0;j<i;j++){A*=10;A+=dig[j];}
if(A==0 || A%k!=0) continue;
for(int j=i;j<10;j++){B*=10;B+=dig[j];}
if(B==0 || B%k!=0) continue;
long a=A/k,b=B/k;
boolean vis[]=new boolean[10];
for(int j=0;j<10;j++) vis[j]=false;
boolean flag=true;
for(long x=a;x>0 && flag;x/=10){
if(vis[(int)(x%10)]) flag=false;
vis[(int)(x%10)]=true;
}
for(long x=b;x>0 && flag;x/=10){
if(vis[(int)(x%10)]) flag=false;
vis[(int)(x%10)]=true;
}
for(long x=k;x>0 && flag;x/=10){
if(vis[(int)(x%10)]) flag=false;
vis[(int)(x%10)]=true;
}
for(int j=0;j<10 && flag;j++) if(!vis[j]) flag=false;
if(flag){
max=Math.max(max,num);
}
}
}
}

}
9857164023
34291ms