Codeforces #1497C1 k-LCM (easy version)

문제

https://codeforces.com/problemset/problem/1497/C1

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, k;
        cin >> n >> k;
        int d = 1;
        while(n%2 == 0 && n != 4){
            n /= 2;
            d *= 2;
        }
        if(n%2 == 0) cout << d*n/2 << " " << d << " " << d << "\n";
        else cout << d*(n-1)/2 << " " << d*(n-1)/2 << " " << d << "\n";
    }
    return 0;
}

n 값이 홀수일 땐 세 수를 (n-1)/2, (n-1)/2, 1 로 나누면 되고, 짝수일 땐 홀수가 될 때까지 계속 2로 나누어 결과값에 나눈 만큼 곱해주면 된다. 단, 값이 4아래로 내려갈 경우 3개의 수로 나눌 수 없으므로 값이 4가 된다면 n/2, 1, 1 에 나눈 만큼 곱한 후 출력한다.

LCM(a1, a2, a3) 값이 n/2 보다 작거나 같도록 하는 n의 구성을 홀수, 짝수 일 때로 나누어 찾고, 분배법칙에 의해서 n == a1 + a2 + a3 이므로 n/d == (a1 + a2 + a3)/d 는 같다는 사실을 이용해 짝수를 홀수 혹은 4로 만들어내는 아이디어를 고수들은 쉽게 찾아내는 걸 보면 정말 대단한 것 같다.