拆拆拆数

Wannafly Day 0 C

第一天唯一做出来的一道题。一道大分类讨论。

分析

这道题就是一道构造题，我们需要将x和y分为n份，使得\(\sum_{i=1}^n a_i = x\),\(\sum_{i=1}^n b_i = y\),并且令\(n\)尽可能地小。此时我们需要根据情况进行分类讨论。

当\(gcd(x,y)=1\)时,这时候\(x\),\(y\)互质，所以\(n\)就为\(1\)。所以直接输出\(x\)和\(y\)即可。
当他们不互质时，首先考虑当\(x\)和\(y\)同奇或同偶的时候。我们可以把第一个数分为\(2\)和\(x-2\)，然后我们将\(y\)分为\(y+1-x\)和\(x-1\)。很明显，首先，\(x-2\)与\(x-1\)互质。然后，因为\(x\),\(y\)同奇偶，所以\(y-x+1\)一定是个奇数，因此其与\(2\)互质。当然，此时需要确保\(x<y\)，若不符合，置换x,y即可。
但是，上面的情况其实需要考虑一种特殊情况。因为题目要求了\(a_i, b_i > 1\)，而当\(x=y\)时，\(x-y+1=1\)，所以不符合题目要求。此时，我们只要令\(a_1 = 2, a_2 = x - 2, b_1 = 3, b_2 = y - 3\)即可。因为\(2\),\(3\)互质，\(x-2\),\(x-3\)互质。
然后我们便需要考虑\(x\),\(y\)奇偶不同的时候了。我们此时先假设\(x\)为奇数，\(y\)为偶数的情况。然后，我们其实需要根据\(x\)的情况再进行分类：
1. 当\(x \mod 3 \neq 2\)时，我们可以将\(x\)分为\(2\),\(x-2\)，并且将\(y\)分为\(y-3\),\(3\)。因为\(x \mod 3 \neq 2\)，所以\((x-2) \mod 3 \neq 0\)，所以它们互质。然后又因为\(y\)是偶数，所以\(y-3\)是奇数，所以它与\(2\)互质。
2. 当\(x \mod 3 = 2\)时，我们则可以将\(x\)分为\(4\),\(x-4\)，并且将\(y\)分为\(y-3\),\(3\)。这样的话，此时因为\(x \mod 3 = 2\)，所以\((x-4) \mod 3 \neq 0\)，所以它们互质。而\(y-3\)又与\(4\)互质，因此满足条件。
3. 此外，我们可能会注意到，\(x-4\)在\(x=5\)时可能为\(1\)，所以我们还需要单独考虑这种情况。因为\(5\)是素数，且\(x\),\(y\)不互质，所以\(y\)一定是它的倍数，所以\(y>=10\)。那么我们便令\(a_1 = 2, a_2 = 3\)，并且\(b_1 = y - 5, b_2 = 5\)即可。

总结

\[ ans = \left\{ \begin{aligned} &a_1 = x,& &b_1 = y,& &\gcd(x,y)=1& \\ &a_1=2, a_2 = x - 2,& &b_1 = 3, b_2 = y - 3,& &x = y& \\ &a_1 = 2, a_2 = x - 2, &&b_1 = y+1-x, b_2 = x-1, &&x \mod 2 = y \mod 2& \\ &a_1 = 2, a_2 = x - 2,& &b_1 = y-3, b_2 = 3,& &x\text{奇}y{偶},\text{且}x \mod 3 \neq 2& \\ &a_1 = 2, a_2 = 3,& &b_1 = y-5, b_2=5,& &x=5,y{偶}& \\ &a_1 = 4, a_2 = x - 4,& &b_1 = y-3, b_2 = 3,& &x\text{奇}y{偶},\text{且}x \mod 3 = 2 & \end{aligned} \right. \]

代码

#include <iostream>
#include <algorithm>

using namespace std;

int n;
long long ans[5][2];
int k = 0;

long long gcd(long long x, long long y)
{
    return x % y == 0? y : gcd(y, x%y);
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        k = 0;

        long long x, y;
        cin >> x >> y;

        if (gcd(x, y)==1)
        {
            n = 1;
            ans[1][0] = x;
            ans[1][1] = y;
        }
        else
        {
            n = 2;

            if (x == y)
            {
                ans[1][0] = 2;
                ans[2][0] = x - 2;
                ans[1][1] = 3;
                ans[2][1] = x - 3;
            }
            else if (x % 2 == y % 2)
            {
                if (y<x)
                {
                    swap(x, y);
                    k = 1;
                }

                ans[1][0] = 2LL;
                ans[2][0] = x - 2;
                ans[1][1] = y + 1 - x;
                ans[2][1] = x - 1;
            }else
            {
                if (x%2==0)
                {
                    swap(x, y);
                    k = 1;
                }
                if (x % 3 != 2)
                {
                    ans[1][0] = 2LL;
                    ans[2][0] = x - 2;
                    ans[1][1] = y - 3;
                    ans[2][1] = 3LL;
                }
                else if (x==5)
                {
                    ans[1][0] = 2;
                    ans[2][0] = 3;
                    ans[1][1] = y - 5;
                    ans[2][1] = 5;
                }
                else 
                {
                    ans[1][0] = 4LL;
                    ans[2][0] = x - 4;
                    ans[1][1] = y - 3;
                    ans[2][1] = 3LL;
                }
            }
        }

        cout << n << endl;
        for (int i = 1; i<=n; i++)
            cout << ans[i][k] << " " << ans[i][k^1] << endl;
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。