\(\color{red}{see}\space \color{green}{in}\space \color{blue}{my}\space \color{purple}{blog}\)
小学生又双叒叕来写题解啦！
其他题解的代码都是 \(O(1)\) 的，对于小学生来说，这也太难分类讨论了。
我们可以用短除模型解决。
设 \(c \times q_1 = a\)，\(c \times q_2 = b\) 并且 \(q_1\) 与 \(q_2\) 互质。
\[a + b + c = n \]\[c \times q_1 + c \times q_2 + c = n \]\[c \times (q_1 + q_2 + 1) = n \]我们只需要枚举 \(c\)，如果 \(c \mid n\) 就停下来，看看 \(q_1\) 与 \(q_2\) 能否构造。
此时，\(q_1 + q_2 = \dfrac{n}{c} - 1\)。
我们再枚举 \(q_1\) 与 \(q_2\)，如果 \(\gcd(q_1, q_2) = 1\)，说明：
\[\begin{cases}a = q_1 \times c\\b = q_2 \times c\\c = c\end{cases} \]是其中一个解。
注意！还有一个坑点，就是 \(a \ne b \ne c\)。
所以，\(q_1\) 与 \(q_2\) 不能等于 \(1\) 哦。
到这就算完了。
如果你担心算法跑得不够快，可以往程序里输入 \(n = 10^9\) 看看会不会超时就行了。
完整代码：
#include <iostream>
#include <cstdio>
using namespace std;
int gcd(int x, int y)
{
if (y == 0) return x;
return gcd(y, x%y);
}
void solve()
{
int n;
scanf("%d", &n);
for (int c = 1; c <= n; c++)
if (n % c == 0)
{
int sum = n / c - 1; //指 q1+q2 的结果。
for (int q1 = 2; q1 <= n-2; q1++) //q1 不能等于 1 所以界线有改变。
{
int q2 = sum - q1;
if (gcd(q1, q2) == 1)
{
printf("%d %d %d\n", q1*c, q2*c, c);
return;
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}
首发：2022-04-19 22:26:23
标签：gcd,space,int,题解,times,color,CF1617B From： https://www.cnblogs.com/liangbowen/p/16622837.html