题解 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)$

程序很简单:

#include <iostream>

using namespace std;

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