算法哈，你咋这么骚！
一篇推文撩拨了资深码农的心弦。为了圆ACM梦，报了字节跳动的主办的《字节跳动冬令营网络赛》。第一次参加ACM又做这种难度的题，被按在地上摩擦在所难免，所以一开始就抱着必死的决心，制定了做出一题就是胜利的战略目标。
下午一点开始比赛，赛程五小时。比赛开始前，拉了一个讨论组和伙计远程讨论，沟通效果确实不咋地，基本是各做各的。由于是英文题目，上来就是一通翻译，通过石墨文档共享翻译的结果，所有题目翻译完基本过了赛程的1/5。现在复盘的话，不如大致浏览下题目，找个题意容易理解的，直接开干，能节省不少时间。我找了下文所述题目作为目标，确实是一个简洁明了的题目。
6：Chiaki有一个n x m网格图，地图上有（n + 1）x（m + 1）个网格点。 她想知道面积为s/2的网格直角三角形的数量。
但看过最终提交的结果才发现自己too young too naivee，这道题的通过率为0/223。
开始解题时，以为是一道简单题，苦苦思索不得要领，经过两个多小时的挣扎，差点放弃比赛。好在有一丝倔强，硬着头皮继续鼓捣，灵机一现，想起了吴恩达教授在深度学习课程上有关卷积网络的卷积算法。
柳暗花明，搞出了如下的解题思路：
step0：在N*M的网格中，求面积为s/2的直角三角形的数量；
step1：在N*M的网格中，求面积为s=l*h的矩形的数量num；
step2：对s进行分解，求出所有(l,h)的组合，即长宽分别为(l,h)的矩形；
step3：重点来了，用卷积公式可知：num=（N-l+1）*(M-h+1)，遍历step2的(l,h)组合，求出所有矩形(l,h)的数量num；
step4：求矩形(l,h)上面积为s/2的三角形数量count；
step5：则矩形(l,h)的三角形总量为num*count，累计所有(l,h)组合即可；
提交Python代码后，发现代码仅通过了9.09% test case，初步怀疑是step2处因式分解存在问题。
代码放在这里了哈，请大神帮忙指点下：
import math
#因式分解
def factoring(n):
ret = []
while n > 1:
for i in range(n-1):
k = i+2
if n % k == 0:
ret.append(k)
n = int(n / k)
break
return ret
#生成n的组合
def combination(n):
ret=[]
if n==1: #为1时特殊处理
ret.append([1,1])#第一组组合
return ret
ret.append([1,n])#第一组组合
ret.append([n,1])#还需要反转下
ids=factoring(n)
#print(ids)
ids = list(set(ids))#去重
#print(ids)
#去掉大于平方根的值
Nsqrt=math.sqrt(n)
ids=[i for i in ids if i <=Nsqrt]
#print(ids)
for a in ids:
b=int(n/a)
ret.append([a,b])
ret.append([b,a])#还需要反转下
return ret
#主函数
def main(N,M,n):
total=0
tempTotal=[]#每个组合中的三角形数量
tempR=[]#每个组合中的矩形数量
res=combination(n)
for item in res:
l=item[0]
h=item[1]
Nl=max(N-l+1,0)#小于0的不行
Mh=max(M-h+1,0)
Rnum=Nl*Mh#矩形数量
Tnum=(h+1)*(l+1)#三角形的数量-4
tempR.append(Rnum)
tempTotal.append(Rnum*Tnum)
total+=Rnum*Tnum
#print(tempR)
#print(tempTotal)
print(total)
return total
#测试部分
INF = 10000
t = int(input())
for i in range(t):
list1 = input().split()
N=int(list1[0])
M=int(list1[1])
S=int(list1[2])
main(N,M,S)
#print(res)
测试用例如下：
