题目链接：
题目意思：
一根长为N的木棒，长度分成若干个三角形，使得任意两个三角形都相似。对应顺序三角形全部全等的为同一种分法，求总共有多少种分法。
解题思路：
数学题。
先考虑分成一个三角形的情况。
不妨设a<=b<=c;
1、当b=c时，a至少为1，所以c<=(n-1)/2
而a<=b 所以n-2*c<=c =>c>=n/3; 故共有(n-1)/2-(n/3)+(n/3?0:1)种。
2、当b<c时，肯定有b<=c-1
此时若a+b>c 则a+b>c-1
如果a,b,c能构成三角形，则a,b,c-1也一定能够构成三角形。
反过来，如果a,b,c-1能够构成三角形，也即a+b>c-1 当a+b！=c时，一定能使a,b,c构成三角形。故可以通过dp[n-1]递推过来，然后减去a+b=c+1的情况。
此时n=2*c+1,c=(n-1)/2 只有当n为奇数的时候才有可能，而a+b=(n-(n-1)/2)，a<=b 所以这种情况共有 （n-(n-1)/2)/2种，化简得（n+1)/4
在考虑有多个三角形的情况。
假设N=a*b 则把b作为一个基本三角形，a个1，作为a个部分，中间有a-1个隔板，每个隔板可选可不选，一共有2^（a-1）种情况。
当所有的隔板都不选的话，就是一个大三角形，所以此时要把，刚才求得的一个三角形中三边不互质的数量减掉。而每个约数，对应的该约数能拆分成一个互质三角形的种数的不互质的三角形，乘以倍数就是大的不互质的三角形。
详见代码：
#include#include #include #include #include #include #include #include #include