Problem43

问题描述：

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

 

 

解决问题：

 

 

package projecteuler;

import java.util.Arrays;

public class Problem43 {

	public static final Long UP = 9876543210L;
	public static final int START = 123;
	
	public static final int HIGH = 9;
	public static int[] Number = new int[9];
	public static final int[] Element = {0,1,2,3,4,5,6,7,8,9};
	
	public static final int[] prime = {2,3,5,7,11,13,17};
	public static long sum = 0;                         
	
	public static long Factorial(int number){
		long r = 1;
		
		for(int i=number; i>1; i--){
			r *= i;
		}
		
		return r;
	}
	
	public static long ai_find(int Last){
		
		Arrays.fill(Number, 0);
		int remain = Last-1;
		int high = HIGH;
		int posititon = 0;
		while(remain!=0){
			long value = Factorial(high);
			long num = 0;
			if(remain>=value){
				num = remain/value;
				remain -= value*num;
				Number[posititon] = (int)num;
			}else{
				Number[posititon] = 0;
			}
//			System.out.println("Position:"+posititon+",value:"+value+",num:"+num+",remain:"+remain);
			posititon++;
			high--;
			
		}
		
		boolean[] matcher = new boolean[10];
		Arrays.fill(matcher, false);
		
		String str = "";
		long value = 0;
		for(int i=0;i<Number.length; i++){
			int index = 0;
			for(int j=0; j<matcher.length; j++){
				if(index==Number[i]&&!matcher[j]){
					str = str + j;
					value = value*10 + j;
					matcher[j] = true;
					break;
				}
				if(!matcher[j]){
					index++;
				}
			}
		}
		
		for(int i=0; i<matcher.length; i++){
			if(!matcher[i]){
				value = value*10 + i;
				str = str + i;
			}
		}
//		System.out.println(str);
//		System.out.println("i:"+value);
		
		return value;
	}
	
	public static void find(int level, boolean[] elements, long result) {

		if (level == 0) {
			if(IsNumber(result)){
					sum += result;
			}
//			System.out.println(result);
			return;
		}
		for (int i = 0; i < elements.length; i++) {
			if (elements[i]) {
				elements[i] = false;
				long tmp = result;
				result = result * 10 + i;
				find(level - 1, elements, result);
				elements[i] = true;
				result = tmp;
			}
			// System.out.println("Level:"+level+",i:"+i+",Result:"+result);
		}
	}
	
	public static boolean IsPandigital(long number){
		boolean[] elements = new boolean[10];
		Arrays.fill(elements, true);
		if(number<=987654321){
			for(int i=1; i<10;i++){
				int cur = (int)number%10;
				if(!elements[cur]){
					return false;
				}
				number = number/10;
				elements[cur] = false;
			}
			return true;
		}else{
			for(int i=0; i<10;i++){
				int cur = (int)number%10;
				if(!elements[cur]){
					return false;
				}
				number = number/10;
				elements[cur] = false;
			}
			return true;
		}
	}
	
	public static boolean IsNumber(long number){
		long init = number;
		int divide = 1000000;
		if(number<=987654321){
			for(int i=0; i<prime.length; i++){
				long value = number/divide;
				if(value%prime[i]!=0){
					return false;
				}
				number = number %10;
				divide = divide/10;
			}
			return true;
		}else{
			number = number%1000000000;
//			System.out.println("number:"+number);
			for(int i=0; i<prime.length; i++){
				long value = number/divide;
//				System.out.println(value);
				if(value%prime[i]!=0){
					return false;
				}
				number = number%(divide*100);
				divide = divide/10;
			}
			return true;
			
		}
	}
	
	public static void main(String[] args){
		
		
		int result = 0;
		boolean[] elements= new boolean [10];
		Arrays.fill(elements, true);
		find(10, elements, result);
		
		System.out.println(IsNumber(1406357289));
		System.out.println(sum);
	}
}