观察如下的算式:
9213 x 85674 = 789314562
左边的乘数和被乘数正好用到了1~9的所有数字,每个1次。
而乘积恰好也是用到了1~9的所有数字,并且每个1次。
请你借助计算机的强大计算能力,找出满足如上要求的9数算式一共有多少个?
注意:
import java.util.HashSet; import java.util.Set; public class Main { static boolean[] book = new boolean[9]; static int[] arr = new int[9]; static int ans; public static void main(String[] args) { dfs(0); System.out.println(ans / 2); } static void dfs(int idx) { if (idx == 9) { for (int i = 0; i <= 7; i++) { int a = atoi(0, i); int b = atoi(i + 1, 8); if (check(a * b)) ans++; } } else { for (int i = 1; i <= 9; i++) { if (!book[i - 1]) { book[i - 1] = true; arr[idx] = i; dfs(idx + 1); book[i - 1] = false; } } } } static boolean check(int res) { String str = "" + res; if (str.indexOf('0') != -1) return false; else { Set<Character> set = new HashSet<Character>(); for (int i = 0; i < str.length(); i++) set.add(str.charAt(i)); return set.size() == 9; } } static int atoi(int s, int e) { StringBuilder str = new StringBuilder(""); for (int i = s; i <= e; i++) str.append(arr[i]); return Integer.parseInt(str.toString()); } }