Moe's CF Life

喵哈喽~！各位Master，今天由我来给大家讲解一道非常可爱的入门构造题哦，嘻嘻。这道题是关于一个叫小C的男孩子对数字“3”的奇妙喜爱，就和本喵喜欢小鱼干一样呢！

题目大意

这道题是说呀，有一个叫小C的同学，他超~喜欢数字3。现在他有一个正整数 n，想让我们帮他把 n 拆分成三个正整数 a, b, c。

拆分需要满足两个条件：

a + b + c = n
a, b, c 这三个数都不能是3的倍数。

题目还很好心地告诉我们，答案一定存在，我们只要找到任意一组解就可以啦，喵~

题解方法

既然题目保证一定有解，而且只要我们随便给一组解就行，那我们就可以偷个懒，用最简单的方法来构造答案啦，喵~ 这就是所谓的构造法。

我们的目标是找到三个不被3整除的正整数，加起来等于 n。

最简单的、肯定不被3整除的正整数是什么呀？当然是 1 和 2 啦！

那我们可以先试着固定其中的两个数，比如 a 和 b。为了让它们肯定不是3的倍数，最简单的选择就是 a=1, b=1 啦！

大胆假设：我们先试试 a = 1, b = 1。那么 c 就必须等于 n - a - b，也就是 n - 2。
检查合法性：现在我们来看看 a=1, b=1, c=n-2 这组解是不是总是符合要求的。
- a 和 b 是正数，也不是3的倍数，完美！
- c = n - 2 是不是正数呢？题目说 n >= 3，所以 c = n - 2 >= 1，肯定是正数，没问题！
- 那 c = n - 2 会不会是3的倍数呢？这就需要分类讨论了喵。
  - 如果 (n - 2) % 3 != 0，那 c 就不是3的倍数，这组解 1, 1, n-2 就完全OK！
  - 但如果 (n - 2) % 3 == 0，那 c 就是3的倍数了，这个方案就失败了，呜...
寻找备用方案：当 (n - 2) % 3 == 0 时（也就是 n % 3 == 2 的时候），我们的第一种假设就不成立了。别急喵！如果 a=1, b=1 不行，我们就换一个嘛！比如 a=1, b=2。这两个数也都是正数，也都不是3的倍数，对吧？
- 新的假设：我们尝试 a = 1, b = 2。
- 那么 c 就变成了 n - a - b，也就是 n - 3。
- 再次检查：我们来看看这个新的 c 在 n % 3 == 2 的情况下是不是乖孩子~
  - c > 0 吗？因为 n % 3 = 2 且 n >= 3，所以 n 最小是5。那么 c = n - 3 >= 2，肯定是正数，过关！
  - c 是不是3的倍数呢？c % 3 = (n - 3) % 3。因为3是3的倍数，所以 (n - 3) % 3 就等于 n % 3。我们现在正是在 n % 3 = 2 的情况下，所以 c % 3 = 2，也不是0！完美解决，喵~！

总结一下我们的策略就是：

先试试 1, 1, n-2。
如果发现 n-2 是3的倍数，那就说明这个方法不行，此时我们改用 1, 2, n-3 作为答案。
这样就一定能找到一组符合要求的解啦！

题解

下面就是具体的代码实现啦，思路和上面讲的一模一样哦。

cpp

#include <iostream>

// 这道题要求我们找到三个正整数 a, b, c 满足：
// 1. a + b + c = n
// 2. a, b, c 都不能被 3 整除。
// 题目保证 n 是一个 3 到 10^9 的整数，并且解总是存在的。
// 我们只需要找到任意一个解。

int main() {
    // 提高一下输入输出效率，是个好习惯喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 我们尝试构造解 a=1, b=1, c=n-2。
    // 这个解是否有效，取决于 c 是否是 3 的倍数。
    if ((n - 2) % 3 != 0) {
        // 如果 c = n-2 不是 3 的倍数：
        // a=1, b=1 显然不是3的倍数。
        // 因为 n >= 3，所以 c = n-2 >= 1，是正数。
        // 所有条件都满足，这是一个有效的解。
        std::cout << 1 << " " << 1 << " " << n - 2 << '\n';
    } else {
        // 如果执行到这里，说明 (n-2) % 3 == 0，即 n % 3 == 2。
        // 此时我们用备用方案 a=1, b=2, c=n-3。
        // a=1, b=2 都不是3的倍数。
        // c = n-3。因为这种情况最小的 n 是 5，所以 c >= 2，是正数。
        // c % 3 = (n-3) % 3 = n % 3 = 2，所以 c 也不是3的倍数。
        // 这也是一个有效的解。
        std::cout << 1 << " " << 2 << " " << n - 3 << '\n';
    }

    return 0;
}

知识点介绍

这道题虽然简单，但涉及到的思想和知识点在算法竞赛中很常用哦！

构造法 (Constructive Approach) 这道题用到的核心方法就是“构造法”。它指的是不通过复杂的算法（比如搜索、动态规划等）去寻找答案，而是根据题目的性质和约束，直接构建出一个或一系列符合条件的解。对于那些保证有解并且让你输出任意解的题目，构造法通常是最简单直接的办法，能帮我们省下很多思考和编码的时间，可以早点去晒太阳了喵~
模运算 (Modular Arithmetic) 解题的关键在于对3取模的性质分析。比如我们通过 (n-2)%3 是否为0来判断 n-2 是否是3的倍数，以及利用 (n-3)%3 == n%3 这个性质来简化我们的证明。熟练掌握模运算的性质，可以帮助我们快速分析问题，找到突破口。就像猫猫能通过微小的声音和气味找到藏起来的猎物一样，嘻嘻。

好啦，今天的题解就到这里啦！是不是很简单，很有趣呢？Master们要多加练习，才能变得更强哦！下次再见，喵~！

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍