BOJ 15948:: 간단한 문제

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

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

$m=1$일 때

\[ 1 + \frac{1}{n} = 1 + \frac{A_1}{B_1} \]

이므로 $B_1 = n A_1$입니다.

$m=2$일 때

\[ 1 + \frac{3}{n} = \left( 1 + \frac{A_1}{B_1} \right) \left( 1 + \frac{A_2}{B_2} \right) \]

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

\[ 1 + \frac{A_2}{B_2} = \frac{n+3}{n+1} \qquad \therefore B_2 = \frac{n+1}{2} A_2 \]

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

\[ 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) \]

따라서 $B_1 = (n/2) A_1$, $B_2 = (n+2) A_2$입니다.

$m=3$일 때

$m=2$일 때의 관찰로부터 $n$이 짝수일 때와 홀수일 때로 나눠 계산해야 한다는 사실을 얻게 됩니다.

1) $n$이 짝수일 때

\[ 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) \]

여기서 $m=2$일 때 방법으로

\[ 1 + \frac{3}{n/2} = \left( 1 + \frac{A_1}{B_1} \right) \left( 1 + \frac{A_2}{B_2} \right) \]

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

2) $n$이 홀수일 때

$B_1 = n A_1$을 대입하면

\[ \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) \]

이 되고, 마찬가지 방법으로 $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;
}