2021省赛 C. 货物摆放
摘要
Title: 2021省赛 C. 货物摆放
Tag: 约数、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2021省赛 C. 货物摆放
-
题意
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 nn 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 LL、WW、HH 的货物,满足 n = L \times W \times Hn=L×W×H。 -
思路
预处理约数，DFS爆搜即可
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40'''
Author: NEFU AB-IN
Date: 2022-01-11 21:07:15
FilePath: \ACM\LanQiao\2021C.py
LastEditTime: 2022-03-16 11:08:01
'''
import sys
sys.setrecursionlimit(int(2e9))
n = 2021041820210418
a = []
ans = 0
def dfs(id, prob):
global ans
if id == 3:
if prob == n:
ans += 1
return
for i in range(len(a)):
if prob * a[i] > n:
return
dfs(id + 1, prob * a[i])
return
i = 1
while i <= n // i:
if n % i == 0:
a.append(i)
if i != n // i:
a.append(n // i)
i += 1
a.sort()
dfs(0, 1)
print(ans)