Description
给定一个正 n 边形,现在要从中选择 m (3≤m≤n) 个顶点,把这些顶点相连,得到一个新的多边形,现要求这个多边形的所有内角都相等。求有多少不同形状的多边形满足条件。
(3≤n≤1012)
Source
Solution
先考虑正多边形怎么做,对于 n 的所有因数 x,我们可以把连续的 x 条线段合成一段,即把 n 条线段分成 nx 段,这样就能得到一个正 nx 边形(nx 至少为 3,所以有 x≤n3)。
举个例子,当 n=12 时,x∈{1,2,3,4} 。
x=1:
x=2:
x=3:
x=4:
对于非正多边形,我们可以在正多边形的基础上进行扩展。
正三边形可以扩展为六边形。
正四边形可以扩展为八边形。
其它正多边形以此类推。比较特殊的是,一条线也能进行扩展,可以得到矩形。
很容易得出结论:对于正 nx 边形(一条线可以看做正二边形,所以这里 x≤n2),我们对它扩展时,把 x 拆成 a+b 的形式(要满足 a<b,不能取 a=b,否则还是正多边形,会重复计算),就能得到一个新的 2nx 边形,一共有 x−12 对 (a,b) 可以取。
很容易得出结论:对于正 nx 边形(一条线可以看做正二边形,所以这里 x≤n2),我们对它扩展时,把 x 拆成 a+b 的形式(要满足 a<b,不能取 a=b,否则还是正多边形,会重复计算),就能得到一个新的 2nx 边形,一共有 x−12 对 (a,b) 可以取。
Code
1 |
|
Related Issues not found
Please contact @heartlessly to initialize the comment