算法哈，你咋这么骚！首次分享于：https://www.jianshu.com/p/6d9491d6871e

一篇推文撩拨了资深码农的心弦。为了圆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=[]
    #为1时特殊处理
    if n==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
#end


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)

测试用例如下：

测试用例