P5436 【XR-2】缘分
题目背景
题目描述
一禅希望知道他和师父之间的缘分大小。可是如何才能知道呢？
一禅想了个办法，他先和师父约定一个正整数 \(n\)，接着他们各自在心里想一个不超过 \(n\) 的正整数。
一禅认为，他和师父心里想的这两个数的最小公倍数越大，则意味着他和师父之间的缘分越大。
师父觉得这个办法很合适，不过他想知道这两个数的最小公倍数最大会是多少。
师父的数学不太好，于是问一禅。一禅也觉得这个问题很困难，他希望你能告诉他答案。
输入格式
本题有多组数据。
第一行一个正整数 $T，表示数据组数。
接下来的 \(T\) 行，每行一个正整数 \(n\)，表示一禅和师父约定的正整数。
输出格式
对每组数据，一行一个正整数，表示答案。
输入输出样例
输入 #1
1
3
输出 #1
6
说明/提示
【样例 1 说明】
不超过 3 的两个正整数的最小公倍数的最大值为 \(\mathrm{lcm}(2,3) = 6\)。
【数据规模与约定】
对 \(50\%\) 的数据，\(1 \le T,n \le 100\)。
对 \(100\%\) 的数据，\(1 \le T \le 100, 1 \le n \le 10^9\)。
【思路】
数学基础
一道很有意思的题目
找规律 + 有点贪心思想
因为这个需要找范围内两个数最大最小公倍数
所以很容易想什么暴力的手法或者
lcm(x,y) = xy / gcd(x,y)
等等的方法
但是在想这些方法的时候很容易忽略掉了最最最简单的方法
但却是很优的方法
你如果想的是前面的方法那么100%的数据很难过掉
但是
可以想一下
因为两个互质的数的最小公倍数是两个数相乘
这样是会让最小公倍数最大化
因为如果不互质的话
需要乘起来之后再去除以gcd
因为毕竟不是最小的还可以约分
所以互质的数一般是会比差不多大小的一对数更优的
所以尽量选取互质的数
而相邻的两个数一定是互质的
所以找两个相邻的数
这两个相邻的数越大乘出来的数就越大
所以选择n和n-1就是最优的这个时候输出n * (n - 1)就行了
完全没必要那么麻烦
注意要开long long ！！！！
【完整代码】
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int T;
cin >> T;
long long n;
for(int i = 1;i <= T;++ i)
{
cin >> n;
if(n == 1)
cout << 1 << endl;
else
cout << n * (n - 1) << endl;
}
return 0;
}