题解 P5436 【【XR-2】缘分】

· · 题解

是挺有缘分的, 我一开始的想法是枚举然后算最大, 然后发现没这么复杂...

首先在 n 个数当中, 找到乘积最大的, 那必定是 n\times(n-1), 然后我们就想这会不会是某两个数的最小公倍数.

根据最小公倍数的定义, 对于两个正整数 p,q, 则 lcm(p,q)=\frac{p\times q}{gcd(p,q)}. 要使得这个等式的值最大, 即令 p\times q 最大, gcd(p,q) 最小. 根据最大公因数的定义, 当 p,q 互素时, gcd(p,q)=1, 此时 gcd(p,q) 的值最小, 使得 lcm(p,q)=p\times q.

且我们知道, 两个正整数 p,q 互素, 即两数没有除了 1 以外的公因数. 那对于 n, n-1 来说, 假设他们有一个不为 1 的公因数 a, 我们可以得到 a|n, a|n-1 ( | 是整除符号, a|b 表示 b 除以 a 的商是一个整数), 如果 a|n, 那么可以得到 a|n-ma (m为大于1的整数), 由 a|n-1 可知, a=1, 与条件不符. 可证正整数 n, n-1 没有除 1 外的公因数, 两数互素, lcm(n,n-1)=n\times(n-1)

因此在不大于 n 的正整数两两组合中, 最大的 lcm(n,n-1)=n\times(n-1)

Update 2024/11/21：

原解析未判断边界条件（我也不知道为什么，可能当时脑子坏掉了吧，整理以前的东西的时候发现的）

需要特判 n=1 时，不难看出此时使得最小公倍数最大的方案是两边都选 1，因此直接特判即可。

#include <iostream>

using namespace std;

int main() {
    unsigned long long t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        if (n == 1)
            cout << 1 << endl;
        else
            cout << n * (n - 1) << endl;
    }
    return 0;
}