当前位置:首页 » Project Euler » 详细页

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?

Solution

对$0~9$做排列组合后__倒序__搜索,假设$A$和$B$连接起来是数字$N$,则$Ka=A,Kb=B$,$N$必然被$K$整除,于是对每个$N$枚举其所有约数,并验证$K$和$(a,b,c...)$包含$0~9$即可,实际上列表只有两个数。

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