题解 | 游游的数值距离

#include <bits/stdc++.h>
using namespace std;
#define int long long

int jc(int x) // 阶乘
{
    int res = 1;
    for (int i = 1; i <= x; i++)
    {
        res *= i;
    }
    return res;
}

void solve()
{
    int n;
    cin >> n;
    // 初始化最小误差和最优解
    // 初始解为 x=1, y=1，此时误差为 |1! * 1 - 1 - n| = n
    int minn = n;
    int xi = 1;
    int yi = 1;

    // 迭代 x 的值。x! 增长很快，只需要检查到 x! - 1 超过 n 即可
    // 12! 约 4.7亿，13! 约 62亿，超过 n 的最大值 10^9
    // 我们只需检查 x = 1, 3, 4, ..., 13 即可。
    for (int x = 1; x <= 13; x++)
    {
        // 约束条件：x != 2
        if (x == 2)
        {
            continue;
        }
        // 计算 te = x! - 1
        int jc_ = jc(x);

        int te = jc_ - 1;

        // 特殊情况：x=1 时，te=0
        if (te == 0)
        {
            // 误差为 |y * 0 - n| = n。
            // 由于初始值已经记录了 x=1 的情况，且 n > 0，这里不用更新。
            continue;
        }

        // te > 0 的情况：目标是找到 y 使得 |y * te - n| 最小

        // 1. 最优 y 的近似值：n/te
        // y_1 是 n/te 的向下取整
        int y_1 = n / te;
        // y_2 是 n/te 的向上取整 (如果 n 不能被 te 整除)
        int y_2 = y_1 + 1;
        // 只需检查 y_1 和 y_2，因为它们是距离 n/te 最近的两个整数
        vector<int> arr;
        if (y_1 > 0)
        { // y 必须是正整数
            arr.push_back(y_1);
        }
        arr.push_back(y_2);

        for (int i : arr)
        {
            // 约束条件：y != 2
            if (i == 2)
            {
                continue;
            }

            // 计算当前误差 E = |i * te - n|
            long long E = abs(i * te - n);

            // 更新最优解
            if (E < minn)
            {
                minn = E;
                xi = x;
                yi = i;

                // 找到最小误差 0，可以直接退出
                if (minn == 0)
                {
                    cout << xi << " " << yi << endl;
                    return;
                }
            }
        }
    }

    // 输出最终找到的最优解
    cout << xi << " " << yi << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}