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;
}