백준 32291번 - x와 x+1의 차이(증명 포함, C++)

문제

• 백준, 실버 1, https://www.acmicpc.net/problem/32291
• 풀이 날짜: 2025.4.15.
• 풀이 시간: 10:49~11:32(43분)
• 사용 언어: C++

문제 해설

해당 문제는 (x+1)의 자신을 제외한 약수를 구하는 문제이다.

우선, 그에 도달하는 과정을 살펴보자.

예제 1의 출력을 보면, x = 998일 때 x+1의 자신을 제외한 약수 1, 3, 9, 27, 37, 111, 333이 정답이 된다.

이를 보고 출력이 되는 모든 양의 정수 k는 (x+1)의 약수라고 가설을 세울 수 있다.

왜 k는 반드시 (x+1)의 약수인가?

가설을 세웠으니 증명해 보자.

다만 고등학생 때 배웠던 귀류법을 가지고 야매로 증명했다 보니, 정확하지 않을 수 있다는 점 양해 바란다. 잘못된 점이 있다면 지적해주면 감사하겠다.

 

가설: 양의 정수 $x$가 주어질 때, $\left\lfloor{\frac{{x}}{{k}}}\right\rfloor$과 $\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor$의 값이 다르게 되는 $x$ 이하의 양의 정수 k는 $(x+1)$의 약수이다.

 

증명: (x+1)의 약수가 아닌 k가 존재한다고 가정하자(귀류법).

이때 $\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor=m$이라 하자.

그러면 $x+1 = k \cdot m + n$(단, m은 양의 정수이고, n은 0<n<k인 양의 정수)인 k, m, n이 존재한다.

$\left\lfloor{\frac{{x}}{{k}}}\right\rfloor$에 대하여 x에 (x+1)의 값을 이용하여 $x = (x + 1) - 1 = k \cdot m + n - 1$와 같이 식을 정리할 수 있다.

그런데 $\left\lfloor{\frac{{x}}{{k}}}\right\rfloor$과 $\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor$가 다르게 되려면,

$$ \left\lfloor{\frac{{x}}{{k}}}\right\rfloor <\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor $$

여야 한다. 그런데 여기에 x 값을 대입하면

$$ \left\lfloor{\frac{{x}}{{k}}}\right\rfloor =\left\lfloor{\frac{{k\cdot m + n - 1}}{{k}}}\right\rfloor=m, \\\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor=\left\lfloor{\frac{{k\cdot m + n}}{{k}}}\right\rfloor=m $$

이 된다. 즉,

$$ \left\lfloor{\frac{{x}}{{k}}}\right\rfloor \not<\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor $$

이 되어 모순이 된다.

따라서 두 값이 다르게 되는 (x+1)의 약수가 아닌 양의 정수 k는 존재하지 않는다.

(x+1)의 자신이 아닌 약수라면 모두 k가 될 수 있는가?

아마도 여기까지 했다면, 직관적으로 (x+1)의 자신이 아닌 약수라면 모두 k가 될 수 있음을 어렴풋이 알 수 있다.

문제를 풀 땐 이 부분을 확실하게 증명하지는 않았는데, 여기에서는 확실하게 하고 싶어서 정리를 해보기로 했다.

 

가설: (x+1)의 자신이 아닌 모든 약수 k에 대하여 $\left\lfloor{\frac{{x}}{{k}}}\right\rfloor$과 $\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor$의 값이 다르다.

 

증명: 정의에 따라 모든 양수 x에 대하여 다음을 만족하는 양의 정수 k, m이 존재한다.

$$ {x + 1} = k \cdot m $$

또한,

$$ x=(x+1)-1=k\cdot m - 1 $$

이다.

따라서

$$ \left\lfloor{\frac{{x}}{{k}}}\right\rfloor = \left\lfloor{\frac{{k \cdot m - 1}}{{k}}}\right\rfloor = m - 1이고 \\\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor = \left\lfloor{\frac{{k \cdot m}}{{k}}}\right\rfloor = m $$

가 되어

$$ \left\lfloor{\frac{{x}}{{k}}}\right\rfloor <\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor $$

즉, (x+1)의 자신이 아닌 모든 약수 k에 대하여 $\left\lfloor{\frac{{x}}{{k}}}\right\rfloor$과 $\left\lfloor{\frac{{x+1}}{{k}}}\right\rfloor$의 값이 다르다.

이 과정을 통해 이 문제는 (x+1)의 자신을 제외한 모든 약수 k를 찾는 문제로 요약할 수 있다.

(x+1) 자신은 제외해야 하는 이유는, x 이하의 양의 정수 k만을 정답으로 인정하기 때문이다.

약수 구하기 알고리즘

이제 (x+1)의 자신을 제외한 약수를 구해보자.

약수 구하기 알고리즘은 단순하게 생각하면 (x+1)을 1부터 (x+1)까지의 정수로 나누면 된다.

그러나 해당 문제는 $x \le 10^{12}$이므로 x 이하의 모든 수로 나누어보려고 하면 시간 초과가 날 가능성이 높다. 일반적으로 알고리즘 문제에서는 c++에서 1억 번 정도의 연산을 1초 내에 수행할 수 있다고 가정을 하고 푸는 경우가 많다. 그래서 $10^{12}$=1,000,000,000,000은 1 경이되어 연산 횟수를 확실히 초과한다.

따라서 약수를 구하는 알고리즘을 조금 최적화해서, 1부터 $\sqrt {x+1}$까지의 정수 i로 수를 나누어 보고, (x+1)이 i로 나누어지면 $i$와 $(x+1) \over i$를 약수로 추가하도록 한다.

이때 주의할 점은 세 가지이다.

1. $i$와 $(x+1) \over i$가 같은 경우가 존재하므로, 이 경우엔 둘 모두 추가하는 대신 i만 추가해 준다.
2. $1 \le i \le \sqrt{x+1}$의 범위에서는 $i \le {(x+1) \over i}$이므로, 오름차순으로 약수를 추가하려고 하면 ${(x+1) \over i}$는 내림차순으로 추가된다. 따라서 별도로 저장한 후, 뒤집어주는 식으로 처리한다.
3. i ≤ sqrt(n)보단 i*i ≤ x가 더 비용이 싸므로, 그렇게 처리하도록 한다(sqrt보단 곱셈 연산이 비용이 싸다).

여기에 long long으로 값을 처리하도록 하면, 문제가 해결된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    long long x;
    vector<long long> factors, big_factors;

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> x;
    x++;
    factors.push_back(1LL);
    
    // get factors
    for (long long i = 2LL; i * i <= x; i++)
    {
        if (x % i == 0LL)
        {
            factors.push_back(i);
            if (i * i < x)
                big_factors.push_back(x / i);
        }
    }
    for (auto it = big_factors.rbegin(); it < big_factors.rend(); it++)
        factors.push_back(*it);

    for (long long f : factors)
    {
        cout << f << " ";
    }

    return 0;
}

고급 문제 해결 수업에서 배웠던 내용이 섞여 있어서 약수 구하기 알고리즘은 좀 더 수월하게 해결할 수 있었던 것 같다.