题意简述 给定
n n n ，将
2 , 3 , … , 3 n + 1 2,3,\dots,3n+1 2 , 3 , … , 3 n + 1 划分成
n n n 组
( a i , b i , c i ) (a_i,b_i,c_i) ( a i , b i , c i ) ，使得每组中的三个正整数构成钝角三角形的三边长。
做法 from 🐍🐍，比官解好。
n = 1 : ( 2 , 3 , 4 ) n = 2 : ( 2 , 4 , 5 ) , ( 3 , 6 , 7 ) n = 3 : ( 2 , 5 , 6 ) , ( 3 , 7 , 8 ) , ( 4 , 9 , 10 ) n=1:(2,3,4)\\
n=2:(2,4,5),(3,6,7)\\
n=3:(2,5,6),(3,7,8),(4,9,10) n = 1 : ( 2 , 3 , 4 ) n = 2 : ( 2 , 4 , 5 ) , ( 3 , 6 , 7 ) n = 3 : ( 2 , 5 , 6 ) , ( 3 , 7 , 8 ) , ( 4 , 9 , 10 ) 提出猜想：将后
2 n 2n 2 n 个数
n + 2 ∼ 3 n + 1 n+2\sim 3n+1 n + 2 ∼ 3 n + 1 相邻两两分组，然后依次找前
n n n 个数
2 n + 1 2~n+1 2 n + 1 配三角形。
但当
n = 4 n=4 n = 4 时出现
( 5 , 12 , 13 ) (5,12,13) ( 5 , 12 , 13 ) 不是钝角三角形。
考虑调大后
2 n 2n 2 n 个数的分组差，具体的选取一个
x x x ，得到
x x x 组边长
( 3 n + 1 − x − i , 3 n + 1 − i ) , i = 0 , 1 , … , x − 1 (3n+1-x-i,3n+1-i),i=0,1,\dots,x-1 ( 3 n + 1 − x − i , 3 n + 1 − i ) , i = 0 , 1 , … , x − 1 然后找前
n n n 个数中最大的
x x x 个配三角形即：
( n + 1 − i , 3 n + 1 − x − i , 3 n + 1 − i ) , i = 0 ∼ n − 1 (n+1-i,3n+1-x-i,3n+1-i),i=0\sim n-1 ( n + 1 − i , 3 n + 1 − x − i , 3 n + 1 − i ) , i = 0 ∼ n − 1 。
考虑这样要满足什么条件：
三角形：( n + 1 − i ) + ( 3 n + 1 − x − i ) > 3 n + 1 − i (n+1-i)+(3n+1-x-i)>3n+1-i ( n + 1 − i ) + ( 3 n + 1 − x − i ) > 3 n + 1 − i
钝角：( n + 1 − i ) 2 + ( 3 n + 1 − x − i ) 2 < ( 3 n + 1 − i ) 2 (n+1-i)^2+(3n+1-x-i)^2<(3n+1-i)^2 ( n + 1 − i ) 2 + ( 3 n + 1 − x − i ) 2 < ( 3 n + 1 − i ) 2
第一个条件取
i = n − 1 i=n-1 i = n − 1 限制最严，得到
x ≤ ⌊ n 2 ⌋ x\leq\lfloor\frac{n}{2}\rfloor x ≤ ⌊ 2 n ⌋ 。
对于第二个条件，我们需要一个引理：
对于一组钝角三角形三边长 a < b < c a<b<c a < b < c a + b > c ∧ a 2 + b 2 < c 2 a+b>c\wedge a^2+b^2<c^2 a + b > c ∧ a 2 + b 2 < c 2 ( a − 1 ) 2 + ( b − 1 ) 2 < ( c − 1 ) 2 (a-1)^2+(b-1)^2<(c-1)^2 ( a − 1 ) 2 + ( b − 1 ) 2 < ( c − 1 ) 2 a + b = c a+b=c a + b = c
证明将平方展开即可。
这告诉我们第二个条件取
i = 0 i=0 i = 0 最严，即
x ( 6 n + 2 − x ) > ( n + 1 − i ) 2 x(6n+2-x)>(n+1-i)^2 x ( 6 n + 2 − x ) > ( n + 1 − i ) 2 ，不难发现
x = ⌊ n 2 ⌋ x=\lfloor\frac{n}{2}\rfloor x = ⌊ 2 n ⌋ 且
n ≥ 2 n\geq 2 n ≥ 2 时必然满足。
那么我们取出这
⌊ n 2 ⌋ \lfloor\frac{n}{2}\rfloor ⌊ 2 n ⌋ 个三角形，记
m = n − ⌊ n 2 ⌋ = ⌈ n 2 ⌉ m=n-\lfloor\frac{n}{2}\rfloor=\lceil\frac{n}{2}\rceil m = n − ⌊ 2 n ⌋ = ⌈ 2 n ⌉ ，则还剩下
3 m 3m 3 m 个数：
2 ∼ 2 + m − 1 , n + 2 ∼ n + 1 + 2 m 2\sim2+m-1,n+2\sim n+1+2m 2 ∼ 2 + m − 1 , n + 2 ∼ n + 1 + 2 m 。
再有一个引理：
对于一组钝角三角形三边长 a < b < c a<b<c a < b < c ( a , b + 1 , c + 1 ) (a,b+1,c+1) ( a , b + 1 , c + 1 )
平方差公式易证。
所以可以加强题目要求：将
2 3 n + 1 2~3n+1 2 3 n + 1 分成
n n n 组，每组中一个
2 ∼ n + 1 2\sim n+1 2 ∼ n + 1 中的数、两个
n + 2 ∼ 3 n + 1 n+2\sim 3n+1 n + 2 ∼ 3 n + 1 的数，且每组都是钝角三角形三边长。
这样就可以直接递归到
2 ∼ 3 m + 1 2\sim 3m+1 2 ∼ 3 m + 1 的情况，然后将
m + 2 ∼ 3 m + 1 m+2\sim 3m+1 m + 2 ∼ 3 m + 1 中的数加上
n − m n-m n − m 即可。
code:
CPP #include <bits/stdc++.h>
int main ()
int n; scanf ("%d" , &n);
int x = 2 , y = n + 2 ;
for (int m = n / 2 ; m; n -= m, m = n / 2 )
for (int i = 1 ; i <= m; i++)
printf ("%d %d %d\n" , x + n - i, y + n * 2 - m - i, y + n * 2 - i);
printf ("%d %d %d\n" , x, y, y + 1 );
return 0 ;
}