题解 | #游游的数值距离#

因为阶乘增长非常快，可能的 $x$ 取值非常有限。对于每个 $x$ （跳过 $x=2$ ），计算 $A = x! - 1$ ，则原式化为 $|y \cdot A - n|$ 。

若 $A = 0$ （即 $x=1$ ）：取 $y=1$ （或其他 $\neq 2$ 的正整数），差值为 $|(1!-1)y - n| = |0 - n| = n$ 。
若 $A > 0$ ：要使绝对值最小，应让 $y$ 尽可能接近 $\frac{n}{A}$ 。最优 $y$ 只可能为 $\lfloor n/A \rfloor$ 或 $\lceil n/A \rceil$ ，排除 $y=2$ 后选取合法的候选值。

枚举每个合法候选 $y$ ，计算差值，更新最小值。

当 $A > n$ 时，最小的差值为 $A-n$ （取 $y=1$ ），且随着 $x$ 增大， $A$ 单调递增，差值只会变大。因此当满足 $A > n$ 且 $A-n \ge$ 当前已知最小差值时，即可终止枚举。若某次差值为 $0$ ，可提前结束。

代码实现

#include <bits/stdc++.h>
#include <limits>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    int ansX, ansY;
    ll fac = 1LL;

    ll minDiff = numeric_limits<ll>::max();
    for (ll x = 1; x <= 13; x++) {
        fac *= x;
        if (x == 2)
            continue;
        ll K = fac - 1;
        if (K == 0) {
            minDiff = n;
            ansX = 1;
            ansY = 1;
            continue;
        }
        ll q = n / K;
        for (ll y = q; y <= q + 1; y++) {
            if (y <= 0 || y == 2)
                continue;
            if (abs(y * K - n) < minDiff) {
                minDiff = abs(y * K - n);
                ansX = x;
                ansY = y;
            }
        }
    }

    cout << ansX << " " << ansY << endl;
}

复杂度分析

时间复杂度：枚举的 $x$ 个数极少，因为 $x!$ 很快超过 $n$ 。对于 $n \le 10^9$ ， $x$ 最多到 $13$ ；对于 $n \le 10^{18}$ ， $x$ 最多到 $20$ 左右。枚举次数是 $O(\log n / \log\log n)$ 级别，可视为常数 $O(1)$ 。每次迭代计算 $A$ 和检查候选 $y$ 均为 $O(1)$ 。
空间复杂度： $O(1)$ ，仅需存储几个变量。