POTION (중, p. 508)

문제#

image.png

어떻게 풀었나?#

$$ \frac{p[i]+\alpha[i]}{r[i]} $$

위 비율이 1이상이되, 모두 같게 만드는 $\alpha[i]$를 찾는 문제이다.

분모인 $r[i]$를 모두 동일하게 만들어주기 위해 최소공배수(LCM, 아래 식에서 $L$로 표기)를 찾는다. 그러고 나면 위에서 언급한 비율이 아래와 같은 식이 된다.

$$ \frac{(p[i]+\alpha[i])\times \frac{L}{r[i]}}{L}\quad(L=LCM_{i=0}^{N-1}(r[i])) $$

여기서 위 비율이 1 이상이 되어야 하므로 분자가 $L$이상이 되는 $\alpha[i]$를 찾아야 하는데, 분자의 값이 $i\text{=}0$부터 $N\text{-}1$까지 모두 동일해야 하므로 분자의 값은

$$ LCM_{i=0}^{N-1}(\frac{L}{r[i]})\times k\;(k \in \N) $$

으로 통일 될 것이다. 이렇게 새롭게 통일 될 값을 간단하게 표현하기 위해

$$ LCM_{i=0}^{N-1}(\frac{L}{r[i]})\times k = L' k $$

으로 다시 쓰면, 모든 i에 대해서

$$ L' k \ge p[i]\times\frac{L}{r[i]} $$

를 만족하는 가장 작은 자연수 k를 찾으면 된다. 단, 비율 값인

$$ \frac{L'k}{L} $$

이 1이상이어야 하므로, 이 부분도 고려해줘야 한다.

이제 우리가 구하고자 하는 $\alpha[i]$는 다음과 같이 나타낼 수 있다.

$$ \alpha[i] = \frac{r[i]L'k}{L} - p[i]\quad\left(k \ge max(\frac{p[i]}{r[i]}\frac{L}{L'}\;,\;\frac{L}{L'})\right) $$

그런데 여기서 문제가 있다. $L$과 $L'$을 직접 구할 수가 없다. 입력으로 들어오는 $r[i]$의 범위가 $[1,1000]$이고 최대 200개까지 들어오는데, 소수만 200개가 들어오면 LCM값들은 거의 $1000^{200}$까지는 아니지만 $100^{200}$까지는 커지지 않을까? (1부터 1000까지의 소수의 개수를 세어보니 168개, 평균 소수값이 453.137정도 된다.)

그러면 $L$과 $L'$을 구하지 않고 이 문제를 해결하는 방법을 찾아야한다. 문제를 풀 당시엔, 느낌상 저 두 수의 관계가 아주 작게 떨어질 것 같다는 생각이 들었다. 그리고 $L$값이 가장 커지는 경우( $r[i]$가 모두 소수인 경우), $L'$이 어떻게 되는지 확인해보았다. $L'$은 $L$과 같았다.

여기서부터 느낌이 왔다. 소수들의 최대공약수(GCD)는 1이니까

$$ \frac{L'}{L}\text{=}1 $$

이 아닐까? 숫자 몇개 넣어보면 $L \ge L'$인 것을 알 수 있어서

$$ \frac{L'}{L} = \frac{1}{GCD} $$

일거라 추측했다. 그리고 $r[i]$의 LCM을 손으로 직접 구하는 과정에서

$$ L = GCD_{i=0}^{N-1}(r[i]) \times LCM_{i=0}^{N-1}(\frac{L}{r[i]}) $$

이 성립하는 것을 확인할 수 있었다. 따라서 구하고자 하는 $\alpha[i]$는 아래와 같이 표현할 수 있다.

$$ \alpha[i] = \frac{r[i]k}{G} - p[i]\quad (\;G= GCD_{i=0}^{N-1}(r[i]),\; k \ge max(\frac{p[i]}{r[i]}G,G)\;) $$

그러면 위 식이 모두 0이상이 되는 최소 자연수 $k$값을 구하여 $\alpha[i]$를 구하면 된다.

정답 코드#

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
int r[201], p[201];
int GCD(int b, int s) {
    if(s==0) return b;
    return GCD(s, b%s);
}
int AllGCD(int* v, int n) {
    int pv = v[0];
    for (int i = 1; i < n; i++) {
        pv = GCD(pv, v[i]);
    }
    return pv;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        for(int i=0; i<n; i++) cin >> r[i];
        for(int i=0; i<n; i++) cin >> p[i];
        int gcd = AllGCD(r, n);

        int mxk=gcd;
        for(int i=0; i<n; i++) {
            int k = (int)((p[i]*gcd + r[i]-1)/r[i]);
            mxk = max(mxk, k);
        }
        for(int i=0; i<n; i++) {
            printf("%lld ", (ll)(r[i]/gcd)*mxk-p[i]);
        }
        puts("");
    }
    return 0;
}

Comment#

사실 처음에는 LCM을 직접 구했었다. 다 구하고 나서 제출해보니 WA를 받아서 좀 생각해보니 LCM을 구하면 안되는 문제였다. 단원 자체도 정수론인데 앞에서 GCD 구하는 방법을 소개했으므로 어쨌든 GCD를 구해서 풀어야 하는 문제일거란 힌트도 있었고, LCM을 구할 수 없으니 $\frac{L'}{L}$이 어떤식으로든 약분될 것이라 생각할 수 있었다. 그리고 이렇게 했음에도 WA를 받았는데, 정답이 int범위를 초과할 수 있는 듯 하다. long long으로 바꾸니 AC를 받을 수 있었다.

추가 TC#

2026년 2/18일 기준으로 아래 입력에 대한 출력값이 0 0 0 0 인 경우에도 AC를 받을 수 있다. 이는 WA이므로, 99 99 99 99 가 출력될 수 있도록 해야한다.

입력#

1
4
100 100 100 100
1 1 1 1

출력#

99 99 99 99
Backward Euclidean Algorithm (p. 506) KMP Forward