算法哈，你咋這么騷！
一篇推文撩撥了資深碼農(nóng)的心弦。為了圓ACM夢，報(bào)了字節(jié)跳動(dòng)的主辦的《字節(jié)跳動(dòng)冬令營網(wǎng)絡(luò)賽》。第一次參加ACM又做這種難度的題，被按在地上摩擦在所難免，所以一開始就抱著必死的決心，制定了做出一題就是勝利的戰(zhàn)略目標(biāo)。
下午一點(diǎn)開始比賽，賽程五小時(shí)。比賽開始前，拉了一個(gè)討論組和伙計(jì)遠(yuǎn)程討論，溝通效果確實(shí)不咋地，基本是各做各的。由于是英文題目，上來就是一通翻譯，通過石墨文檔共享翻譯的結(jié)果，所有題目翻譯完基本過了賽程的1/5。現(xiàn)在復(fù)盤的話，不如大致瀏覽下題目，找個(gè)題意容易理解的，直接開干，能節(jié)省不少時(shí)間。我找了下文所述題目作為目標(biāo)，確實(shí)是一個(gè)簡潔明了的題目。
6：Chiaki有一個(gè)n x m網(wǎng)格圖，地圖上有（n + 1）x（m + 1）個(gè)網(wǎng)格點(diǎn)。 她想知道面積為s/2的網(wǎng)格直角三角形的數(shù)量。
但看過最終提交的結(jié)果才發(fā)現(xiàn)自己too young too naivee，這道題的通過率為0/223。
開始解題時(shí)，以為是一道簡單題，苦苦思索不得要領(lǐng)，經(jīng)過兩個(gè)多小時(shí)的掙扎，差點(diǎn)放棄比賽。好在有一絲倔強(qiáng)，硬著頭皮繼續(xù)鼓搗，靈機(jī)一現(xiàn)，想起了吳恩達(dá)教授在深度學(xué)習(xí)課程上有關(guān)卷積網(wǎng)絡(luò)的卷積算法。
柳暗花明，搞出了如下的解題思路：
step0：在N*M的網(wǎng)格中，求面積為s/2的直角三角形的數(shù)量；
step1：在N*M的網(wǎng)格中，求面積為s=l*h的矩形的數(shù)量num；
step2：對s進(jìn)行分解，求出所有(l,h)的組合，即長寬分別為(l,h)的矩形；
step3：重點(diǎn)來了，用卷積公式可知：num=（N-l+1）*(M-h+1)，遍歷step2的(l,h)組合，求出所有矩形(l,h)的數(shù)量num；
step4：求矩形(l,h)上面積為s/2的三角形數(shù)量count；
step5：則矩形(l,h)的三角形總量為num*count，累計(jì)所有(l,h)組合即可；
提交Python代碼后，發(fā)現(xiàn)代碼僅通過了9.09% test case，初步懷疑是step2處因式分解存在問題。
代碼放在這里了哈，請大神幫忙指點(diǎn)下：
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時(shí)特殊處理
? ? ? ? ret.append([1,1])#第一組組合
? ? ? ? return ret
? ? ret.append([1,n])#第一組組合
? ? ret.append([n,1])#還需要反轉(zhuǎn)下
? ? 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])#還需要反轉(zhuǎn)下
? ? return ret
#主函數(shù)
def main(N,M,n):
? ? total=0
? ? tempTotal=[]#每個(gè)組合中的三角形數(shù)量
? ? tempR=[]#每個(gè)組合中的矩形數(shù)量
? ? 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#矩形數(shù)量
? ? ? ? Tnum=(h+1)*(l+1)#三角形的數(shù)量-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)
測試用例如下：
