Code shoe set - mt3111 · assignment

---

assignment

• assignment .

The time limit ：1 second
Space restriction ：64M

---

Title Description

The adventure group is exploring in a wonderful secret place , In front of me is the reward level of the secret place , The checkpoint mechanism is as follows ： Random given M Gold coin , If you can find three that are not greater than M The positive integer （ Can be the same ）, Find their least common multiple S, Then the adventure group can get S Gold coins . In order to get the most gold coins , It is unanimously decided that you, the team think tank, will be entrusted with the task , Find out S The maximum of .

---

Input description

Enter a positive integer n

• 1<=n<=1e6

---

Output description

Output the least common multiple of the three numbers in the question S The maximum of

---

Example 1

Input

10

Output

630

Topic analysis

The title of this problem can be summarized as ： Seek from $1\sim n$ The maximum value of the least common multiple of any three numbers .

This problem is actually a mathematical problem . The complexity of trying to enumerate three numbers violently is $O(n^3)$, It's bound to time out .

So we need to use the mathematical properties of Coprime . The following conclusions may not prove , But it does not affect the passage of this question .

Obviously , When three numbers are coprime , The least common multiple of three numbers is the largest .

Method 1 ： The mathematical formula

• $n$ In an odd number of ,$n$、$n-1$、$n-2$ Coprime
• $n$ For even when

  • $n$ Can be $3$ Divisible time ,$n-1$、$n-2$、$n-3$ Coprime
  • $n$ Can not be $3$ Divisible time ,$n$、$n-1$、$n-3$ Coprime

Some people may not be convinced , Why the above properties . Here interested students can go to search , But this article does not prove it here , Because there is another way .

Method 2 ： Local violence

I really encounter such a problem , I don't know what to do with the mathematical formula of method one ？

No problem , Greed can pass .

First of all, I want to take the opportunity as big as possible , We have to get these three numbers as large as possible .

So we can $n$ In the vicinity of . The time limit for this question is $1s$, Here $1s$ In the time of , Conduct $10^6$ The amount of calculation is not excessive ！

All we need to do is $[\max (1,n-100),n]$ Enumeration within the scope of $i,j,k$, Can be in $10^6$ Get the best answer in the level of computation .

Method 3 ： The formula + No brain

The second method is mindless computing , Method 2 is adopted because “ Do not know the mathematical formula of method one ”. In fact, we just need to $[\max (1,n-3),n]$ The best answer can be obtained by enumerating three numbers within the range of .（ For the time being, it is recorded as method 3 ： The formula + No brain ）

AC Code

Method 1 ： The mathematical formula

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    
    ll n;
    cin >> n;
    if (n % 2) {
    
        cout << n * (n - 1) * (n - 2) << endl;
    }
    else {
    
        if (n % 3 == 0) {
    
            cout << (n - 1) * (n - 2) * (n - 3) << endl;
        }
        else {
    
            cout << n * (n - 1) * (n - 3) << endl;
        }
    }
    return 0;
}

Method 2 ： Local violence

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll i = max(1ll, n - 100); i <= n; i++)
        for (ll j = max(1ll, n - 100); j <= n; j++)
            for (ll k = max(1ll, n - 100); k <= n; k++) {
    
                /* // Error!  There is a wrong method in the comments  400 400 401 Of gcd by 1,400*400*401/1/1 != 400 * 401 ll gcd = __gcd(__gcd(i, j), k); ans = max(ans, i * j * k / gcd / gcd); printf("i = %lld, j = %lld, k = %lld, __gcd(i, j, k) = %lld, GBS = %lld\n", i, j, k, gcd, i * j * k / gcd / gcd); */
                ll thisAns = i * j / __gcd(i, j);
                thisAns = thisAns * k / __gcd(thisAns, k);
                ans = max(ans, thisAns);
            }
    cout << ans << endl;
    return 0;
}

Method 3 ： The formula + No brain

Running time is greatly reduced

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll i = max(1ll, n - 3); i <= n; i++)
        for (ll j = max(1ll, n - 3); j <= n; j++)
            for (ll k = max(1ll, n - 3); k <= n; k++) {
    
                ll thisAns = i * j / __gcd(i, j);
                thisAns = thisAns * k / __gcd(thisAns, k);
                ans = max(ans, thisAns);
            }
    cout << ans << endl;
    return 0;
}

Update the weekly competition solution of elite class in advance every week , Focus , Neverlost

Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125538415