法一
/*
再每一个a里去找c,他们共用一个st数组,可以解决重复出现数字
通过ac确定b,b不能出现<=0 b出现的数不能和ac重复*/import java.util.Scanner;public class Main {static int n,res;static boolean[] st = new boolean[15];static boolean[] backup = new boolean[15];static int[] data = new int[15];public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs_a(1,0);System.out.println(res);}public static void dfs_a(int u,int a){if (a > n) return;//每一个a里去找不出现a中数字的c的全排列if (a > 0)dfs_c(u,a,0);for(int i = 1;i <= 9;i++){if (!st[i]){st[i] = true;dfs_a(u + 1,a * 10 + i);st[i] = false;}}}public static void dfs_c(int u,int a,int c){if (u == 9) return;if (c > 0)//通过ac确定bif (check(a,c)) res++;for(int i = 1;i <= 9;i++){if (!st[i]){st[i] = true;dfs_c(u + 1,a,c * 10 + i);st[i] = false;}}}public static boolean check(int a,int c){//n 和 c 可能会溢出long b = n * (long)c - a * c;if (b <= 0) return false;backup = st.clone();while (b > 0){//b的每一位不能再之前出现过,并且不能等于0int ge = (int)b % 10;b /= 10;if (backup[ge] || ge == 0) return false;backup[ge] = true; //记得出现出的数字也要标记一下}for(int i = 1;i <= 9;i++){if (!backup[i]) return false;}return true;}
}
法二
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int n;// 目标数static int[] a = new int[10];// 全排列数组static boolean visi[] = new boolean[10]; // 放入数组就进行记录，避免重复使用static int ans = 0;// 统计public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(1);System.out.println(ans);}//枚举全排列public static void dfs(int u){if(u == 10){check();return;}for (int i = 1; i <= 9; i++){if(!visi[i]){visi[i] = true;a[u] = i;dfs(u + 1);// 回溯visi[i] = false;}}}//切割成三份是否满足题目给定式子public static void check(){for(int i = 1 ; i <= 7;i++){//a最多可以取七位,取前七位即可,全排列有对称关系int num1 = Test(1, i);//枚举num1所有可能得长度//num1再继续加下面num2与num3也是超标已经超过了N,没有必要再继续if(num1 >= n)continue;for(int j = i + 1 ; j <= 8;j++){int num2 = Test(i + 1,j);//分子数int num3 = Test(j + 1, 9);//分母数if(num2 % num3 == 0 && num1 + num2 / num3 == n){//进行判断ans++;}}}}public static int Test(int start,int end){int number1 = 0;for (int i = start; i <= end; i++){number1 = number1 * 10 + a[i];}return number1;}
}
