python-带分数（巧解，时间复杂度低）

解题思路:

首先对题目进行分析，我们要处理的数一共有三个，一个是整数，一个是分母，一个是分子。

接下来说一下本题的解法。

根据数学规律，我们可以得知，两数相除，如果我们要得到一个n位数的商，只有两种情况，①分子比分母多（n-1）位。②分子比分母多n位。

举个例子说明以下。假如我们想得到一个2位数的商，当分子比分母多1位时，100/99<=商<=999/10，当分子比分母多2位时，1000/99<=商<=9999/10

当分子比分母多3位时，商>=10000/99，这时我们最小也会得到一个三位数的商。那么知道了这个规律，接下来就容易解题了。

①我们假设此时的整数部份有m位，要求的商为n位。则可分配的还有9-m位。设分母为a位，则分子为a+k位（k=n-1或者k=n），我们可以得到一个简单的数学关系式a+a+k = 9-m，则a = (9-m-k)/2

通过观察结果我们发现两种情况每次只能成立一种，当k=n-1时，如果9-m-k是偶数，那么当k=n时，9-m-k一定为奇数，反之亦然。

②接下来我们就对整数的取值情况进行遍历，然后对分母的情况进行遍历，将分子直接算出来，如果最后的整数，分子，分母符合题目要求，我们就对结果进行+1。

注意事项:

参考代码:

def f(n):  
    ans = 0  
  
    for i in range(1,n):   #对整数部份进行遍历
        if len(str(i)) != len(set(str(i))) or ('0' in str(i)):  #判断整数部份是否符合条件
            continue  
  
        k = len(str(n-i))-1   #算出分子比分母最少要多几位
        m = 9-len(str(i))     #剩余可分配的位数
        if (m-k)%2 == 0:      #判断两种情况中那种情况是成立的
            x = (m-k)//2  
            if x <= 0:  
                continue  
            for j in range(10**(x-1),10**x):  #对分母的取值进行遍历
                if len(str(j)) != len(set(str(j))) or ('0' in str(j)):  
                    continue  
                k = j*(n-i)  #计算出分子
                temp = str(i)+str(j)+str(k)  
                if len(temp) == 9 and len(set(temp)) == 9 and '0' not in temp:  #判断整数，分子，分母是否符合题目要求
                    ans = ans + 1      
        else:  
            x = (m-k-1)//2  
            if x <= 0:  
                continue  
            for j in range(10**(x-1),10**x):  
                if len(str(j)) != len(set(str(j))) or ('0' in str(j)):  
                    continue  
                k = j*(n-i)  
                temp = set(str(i)+str(j)+str(k))  
                if len(temp) == 9 and len(set(temp)) == 9 and '0' not in temp:  
                    ans = ans + 1  
  
    print(ans)  
              
  
if __name__ == '__main__':  
    n = int(input())  
    f(n)