[BOJ] 25342: 최대 최소공배수

https://www.acmicpc.net/problem/25342

BOJ - 최대 최소공배수

문제 유형: 정수론, 수학, 그리디

문제 난이도 : Gold III

 

제한

시간: 1초

메모리: 1024MB

 

문제

 1부터 N까지의 수가 있다. 최소공배수가 최대가 되도록 서로 다른 3개의 수를 선택해 보자.

 

입력

첫째 줄에 테스트케이스의 개수 T가 주어진다. (1≤T≤1000)

둘째 줄부터 T개의 줄에 각각 자연수 N$N$이 주어진다. (3≤N≤100000)

 

출력

각 테스트케이스마다, 최소공배수의 최댓값을 한 줄에 하나씩 차례대로 출력한다.

 

풀이

중점은 세 수의 곱을 최대화하면서 gcd의 크기를 작게 하도록 하는 것이다.

n이 홀수인 경우, lcm(n, n-1, n-2)가 가장 크다고 할 수 있다.

n과 n-2가 홀수가 되어 gcd의 크기가 작아져서 lcm의 크기가 최대가 된다.

n과 n-1은 서로소이고, n-1과 n-2사이도 그렇다.

연속된 두 수는 반드시 서로소이기 때문이다.

그리고, n과 n-2는 둘다 홀수로, gcd의 크기가 작을 확률이 크다.

 

n이 4 이상의 짝수인 경우, lcm(n, n-1, n-3)이 가장 크다고 할 수 있다.

n-1과 n-3이 홀수가 되어 gcd의 크기를 최소한으로 하면서도 가장 큰 곱을 만들 수 있다.

 

n이 3의 배수인 경우, lcm(n-1, n-2, n-3)이 가장 크다고 할 수 있다.

3의 배수는 홀수이거나 짝수일 수 있는데, 그들은 각각 n(n-1)(n-2)/2, n(n-1)(n-3)/3의 lcm을 갖는데,

이 수들은 (n-1)(n-2)(n-3)보다 작은게 자명하다.

 

즉, 이 세 가지 케이스 중에서 가장 큰 값을 고르면 된다.

 

코드

C++

#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
  return a*b/gcd(a,b);
 }

ll lcm(ll a, ll b, ll c) {
  return a*b*c/gcd(a, lcm(a,b));
}

ll solution(int n) {
  ll res = max(lcm(n, n-1, n-2), max(lcm(n, n-1, n-3), lcm(n-1, n-2, n-3)));

  return res;
}

int main (int argc, char *argv[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0); int t, n;
  cin >> t;

  for(int i = 0; i < t; ++i) {
    cin >> n;
    ll l = solution(n);
    cout << l << "\n";
  }

  return 0;
}