题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
python 代码
import copy
n=int(input())
cnt=0
used=[0]*25
#一共仨剪枝策略 俩能用
#1. 剪枝策略1:(分子)的位数 一定 ≥ c(分母)的位数,不然结果不可能是整数 ->不好而且超时
#2. 剪枝策略2:由于a、b、c至少各1位,而一共9个数,所以a、b、c最多7位 ->能通过但稍慢
#3. 剪枝策略3:abc相加位数小于9 ->这么简单粗暴又好用,快了不少
def check(a,c):
b=(n-a)*c
nums=set('123456789')
tmp=str(a)+str(b)+str(c)
if len(tmp)==9 and set(tmp)==nums:
return True
return False
def dfs_c(a,c):
global cnt
b=c*(n-a)
if len(str(a))+len(str(b))+len(str(c))>9:
return
if check(a,c):
cnt+=1
for i in range(1,10):
if not used[i]:
used[i]=1;
dfs_c(a,c*10+i)
used[i]=0
def dfs_a(a):
if a>=n:
return
if(a):
dfs_c(a,0) #第三个数表示c的大小
for i in range(1,10):
if not used[i]:
used[i]=1;
dfs_a(a*10+i)
used[i]=0
dfs_a(0) #前为用了几个数字,后为a为多少
print(cnt)
```