题目描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。
类似这样的带分数，100 有 11 种表示法。
输入描述
从标准输入读入一个正整数 N\ (N<1000 \times 1000)N (N<1000×1000)。
输出描述
程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
输入输出样例
示例
输入
100
输出
11
运行限制
- 最大运行时间：3s
- 最大运行内存: 64M
思路：
输入一个数n，要求我们用1，2，3，4，5，6，7，8，9，九个数且每个数只能用一次地根据n=a+b/c这个式子将n表示出来。
在这道题中，我们可以将九个自然数进行全排列并且分隔，假设现在有一个1--9的自然数的排序，我们把他分割成a|b|c。进行分割时，由n=a+b/c可知，a的长度必然小于等于n，故我们只要求遍历a<=len(n)的部分就可以了。
因为我们会遍历所有的a，所以每一次循环（n-a）的值我们是可以得到的，我们假设此刻全排列的b,c都是存在的。那么，下一步就是确定b和c的值，那么他们两个的值又该如何确定呢？根据题意，1—9个数只出现一次，所以如果我们知道了b的尾数，此时排列可知，那么我就可以确定b和c的分割点，根据a|b|c我们就可以确定b和c的值。可是我们又该如何求b的尾数呢？
由n=a+b/c，得b=(n-a)*c，n-a我们是知道的，c我们不知道，但是c的尾数我们知道，就是全排列的最后一位num[-1]，那我们直接将num[-1]*（n-a)然后再%10，不就得到了b的尾数吗？尾数我们得到了，那么b，c的值我们就可以确定。（注：在这个过程中我们会去掉一些不符合实际的情况）
接下来我们就要判定我们得到的a,b,c,是不是符合条件的，如果条件都符合，则我们一开始的假设成立，此刻全排列的b,c都是存在的，cnt++.如果不符合条件，则假设失败，a取下一个值或者进入进入下一个排列。
1. from itertools import * 2. n = int(input()) 3. bit = len(str(n)) # n的位数 4. cnt = 0 5. for num in permutations("123456789"): 6. a, b, c = 0, 0, 0 7. for al in range(bit): # al: a的位数，a肯定比n短 8. a = int("".join(num[:al+1])) #一个a 9. bLast = (n - a) * int(num[-1]) % 10 #b的尾数，(n-a)c%10 10. if bLast == 0: continue #b的尾数不可能等于0，因为只用到1~9 11. bl = num.index(str(bLast)) #根据b的尾数，确定b的长度 12. if bl <= al or bl >= 8: continue #b的尾数不会》=8也不会在a中 13. b = int("".join(num[al+1:bl+1])) 14. c = int("".join(num[bl+1:])) 15. if b % c == 0 and n == a + b // c:#判断是否符合条件,//:整数除法 16. cnt += 1 17. print(cnt)
感谢蓝桥杯--罗勇军老师的指导，罗老师yyds
