Up

BOJ 15948:: 간단한 문제

$m$에 1, 2, 3을 넣어보면 규칙이 보입니다.

$m$이 1일 때
\begin{equation*} 1 + \frac1n = 1 + \frac{A_1}{B_1} \end{equation*}

이므로 $B_1=nA_1$입니다.

$m$이 2일 때
\begin{equation*} 1 + \frac{3}{n} = \left( 1 + \frac{A_1}{B_1} \right) \left( 1 + \frac{A_2}{B_2} \right) \end{equation*}

에서 $B_1=nA_1$을 대입해봅시다.

\begin{equation*} 1 + \frac{A_2}{B_2} = \frac{n+3}{n+1} \qquad \therefore B_2 = \frac{n+1}{2} A_2 \end{equation*}

$n$이 홀수면 답이 되지만 짝수면 안 됩니다. 이 때는 아래와 같이 식을 바꿔서 해결 가능합니다.

\begin{equation*} 1 + \frac{3}{n} = \frac{n+3}{n} = \frac{n+2}{n} \cdot \frac{n+3}{n+2} = \left( 1 + \frac{1}{n/2} \right) \left( 1 + \frac{1}{n+2} \right) \end{equation*}

이 경우 $B_1=(n/2)A_1$, $B_2=(n+2)A_2$입니다.

$m$이 3일 때

위의 관찰로부터 $n$이 짝수일 때와 홀수일 때로 나눠야 한다는 사실을 유추해볼 수 있습니다. 먼저 $n$이 짝수이면

\begin{equation*} 1 + \frac{7}{n} = \frac{n+6}{n} \cdot \frac{n+7}{n+6} = \left( 1 + \frac{3}{n/2} \right) \left( 1 + \frac{1}{n+6} \right) \end{equation*}

여기서 $m$이 2일 때 사용한 방법으로

\begin{equation*} 1 + \frac{3}{n/2} = \left( 1 + \frac{A_1}{B_1} \right) \left( 1 + \frac{A_2}{B_2} \right) \end{equation*}

를 만족하는 $B_1$과 $B_2$를 구하고 $B_3=(n+6)A_3$로 두면 됩니다.

$n$이 홀수라면 $B_1=nA_1$을 대입하여

\begin{equation*} \frac{n+7}{n+1} = 1 + \frac{3}{(n+1)/2} = \left( 1 + \frac{A_2}{B_2} \right) \left( 1 + \frac{A_3}{B_3} \right) \end{equation*}

를 얻고, 마찬가지 방법으로 $B_2$와 $B_3$를 구하면 됩니다.

위 방법을 모든 $m$에 대해 확장하면 문제를 풀 수 있습니다. 사실 결론적으로 주어진 등식을 만족하는 수열 $B$는 항상 존재합니다. 

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
using Vullit = vector<ull>::iterator;

void solve(ull n, ull m, Vullit a, Vullit b) {
    if (m == 1) {
        b[0] = n * a[0];
        return;
    }
    if (n % 2 == 1) {
        b[0] = n * a[0];
        solve((n+1)/2, m-1, a+1, b+1);
        return;
    }
    solve(n/2, m-1, a, b);
    b[m-1] = (n + (1LL << m) - 2) * a[m-1];
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ull n, m;
    cin >> n >> m;

    vector<ull> a(m), b(m);
    for (ull i = 0; i < m; i++)
        cin >> a[i];

    solve(n, m, a.begin(), b.begin());

    for (ull i = 0; i < m; i++)
        cout << b[i] << ' ';

    return 0;
}