# IOICJ 57 LCM Problem ( Math, Search )

Problem Description:
Given N, you want to know max{ LCM(x,y,z), 1≤x,y,z≤N }.

Constraints:
1≤T≤1000
1≤n≤1e6

Sample Input:
3
7
9
100

Sample Output:
210
504
960300

Solution:
It is obvious that we would like some of the largest x, y, z, such that they are co-prime. It is intuitive to search not values that are too low.

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void dfs( int v, vector< int > &chose, ll &best, int dpt ){
if( dpt == 4 ) return;
int ng = 0;
for( int i = 0; i < chose.size(); ++i ){
ng |= __gcd( chose[ i ], v ) > 1;
}
dfs( v - 1, chose, best, dpt + 1 );
if( not ng ){
chose.emplace_back( v );
if( chose.size() < 3 ){
dfs( v - 1, chose, best, 0 );
} else{
best = max( best, 1LL * chose[ 0 ] * chose[ 1 ] * chose[ 2 ] );
}
chose.pop_back();
}
}

signed main(){
ios::sync_with_stdio( 0 );
int T; cin >> T;
for( int ti = 0; ti < T; ++ti ){
int N; cin >> N;
if( N == 1 ) cout << 1 << endl;
else if( N == 2 ) cout << 2 << endl;
else if( N == 3 ) cout << 6 << endl;
else if( N == 4 ) cout << 12 << endl;
else if( N == 5 ) cout << 60 << endl;
else{
ll ans = 0;
for( int i = N; i >= N - 5; --i ){
vector< int > chose = { i };
dfs( i - 1, chose, ans, 0 );
}
cout << ans << endl;
}
}
return 0;
}
```