Problem Description
Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.
But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than n. Can you help me to find the maximum possible least common multiple of these three integers?
Input
The first line contains an integer n (1 ≤ n ≤ 10^6) — the n mentioned in the statement.
Output
Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than n.
Sample Input
9
Sample Output
504
Source
WJMZBMR
Manager
题目类型：LCM
算法分析：题目要求的是任意3个大于等于1小于等于n的数的最小公倍数的最大值。由于有相邻两个自然数a、a+1的最大公约数是1，即意味着相邻两个数的最小公倍数是a *(a+1)。如果n是奇数，则可易知n*(n-1)*(n-2)就是最大的LCM。如果n是偶数，则判断n是否是3的倍数。如果是，则(n-1)*(n-2)*(n-3)就是结果，反之，结果是n*(n-1)*(n-3)。对于后面的结论，进行一个简单的说明：首先(n-1)*(n-2)*(n-3)要比(n-1)*n*(n-3)小，但是如果3|n，则n和n-3的最小公倍数就不是1了。会导致结果变小，所以此时不应该选择这种情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; int main() { // ifstream cin("aaa.txt"); long long n; while (cin >> n) { if(n == 1) cout << "1" << endl; else if (n == 2) cout << "2" << endl; else { if (n & 1) cout << n * (n - 1) * (n - 2) << endl; else { if (n % 3) cout << n * (n - 1) * (n - 3) << endl; else cout << (n - 1) * (n - 2) * (n - 3) << endl; } } } return 0; } |
- « 上一篇：vijos1448
- fzu1669：下一篇 »