关于一个关于最小公倍数的数学问题

Question

给定一个正整数 n，请找出一组互不相同的正整数 a,b,c，使得：

• a+b+c=n
• gcd(a,b)=c

其中 gcd(x,y) 表示 x 和 y 的最大公因数。
求思路，谢谢！

Answer 1

设a = xc, b=yz, a+b+c = (x+y+1)c = n, 其中x和y互质, 那不就是把遍历1到sqrt(n), 每次遍历判断n能不能被i整除, 能的话设另一个因数是r, 显然x+y=r-1, 再把r-1分解成两个互质的数x, y的和. 有个定理, 两个互质的数的和, 一定与这两个数互质, 所以再遍历j从2到sqrt(r-1), 如果j和r-1互质, 那么x = j, y=r-1-j