标题：带分数

    100 可以表示为带分数的形式：100 = 3 + 69258 / 714

    还可以表示为：100 = 82 + 3546 / 197

    注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

    类似这样的带分数，100 有 11 种表示法。

题目要求：

从标准输入读入一个正整数N (N<1000*1000)

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

例如：

用户输入：

100

程序输出：

11

再例如：

用户输入：

105

程序输出：

6

资源约定：

峰值内存消耗（含虚拟机） < 64M

CPU消耗  < 3000ms

 

这一题主要是熟悉全排列和数字的组合。

1 import java.util.Scanner; 2  3 public class A { 4  5     static int vis[] = new int[1000 * 1001]; 6     static int a, b, c, ans; 7  8     public static void main(String[] args) { 9         int[] num = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9 };10         Scanner scanner = new Scanner(System.in);11         int n = scanner.nextInt();12         per(num, 0);13         System.out.println(vis[n]);14     }15 16     public static void per(int[] num, int start) {17         if (start == num.length) {18             ser(num);19             return;20         }21         for (int i = start; i < num.length; i++) {22             swap(num, start, i);23             per(num, start + 1);24             swap(num, start, i);25         }26     }27 28     public static void swap(int[] num, int n, int m) {29         int t = num[n];30         num[n] = num[m];31         num[m] = t;32     }33 34     public static void ser(int[] num) {35         for (int i = 0; i <= 6; i++) {36             for (int j = i + 1; j <= 7; j++) {37                 a = 0;38                 b = 0;39                 c = 0;40                 ans = 0;41                 for (int k = 0; k <= i; k++) {42                     a = a * 10 + num[k];43                 }44                 for (int k = i + 1; k <= j; k++) {45                     b = b * 10 + num[k];46                 }47                 for (int k = j + 1; k <= 8; k++) {48                     c = c * 10 + num[k];49                 }50                 if (b % c == 0) {51                     ans = a + b / c;52                     if (ans < 1000000)53                         vis[ans]++;54                 }55             }56         }57     }58 59 }