백준 30481 - Forward and Backward

문제 번역

하나의 숫자 $N$을 입력받습니다. $N$을 $X$진수로 변환했을 때, 팰린드롬이 되는 모든 $X$값을 출력합니다. 만약 이러한 $X$값이 없다면 *을 출력합니다.

step 1

$N$이 2일 땐 *을 출력합니다. 그 외의 경우에는 $N-1$진수로 변환하면 항상 $11_{(N-1)}$이 나오므로 답이 1개 이상 존재합니다.

변환 결과가 2자리인 경우와 3자리 이상인 경우로 구분해 보겠습니다. 3자리 이상인 경우부터 해결하겠습니다.

3자리 이상인 경우에는 직접 계산합니다. $X$를 2부터 시작하여 $X$진수로 변환한 후 팰린드롬 여부를 확인합니다. $X>=\sqrt{N}$ 일 때 2자리가 되므로 이 과정은 $O( \sqrt{N} )$만큼 걸립니다.

step 2

1. 2자리인 경우 $X>=\sqrt{N}$ 입니다. 두번째 자리에 $ \sqrt{N} $보다 큰 수가 들어가면 계산 결과가 $N$을 넘어갑니다.
2. 변환 결과가 팰린드롬이므로 첫번째 자리와 두번째 자리가 같아야 합니다.

그렇다면 변환 결과가 $11, 22, ..., \sqrt{N} \sqrt{N} $을 만족하는 진수가 있는지 확인하면 됩니다.

결과가 $yy$라고 하면 $y*X+y=N, X=\frac{N-y}{y}$가 정수인지 확인합니다. 이때 $X$진수에는 $0$부터 $X-1$까지의 수만 들어갈 수 있으니 $ \frac{n-y}{y} > y$인지도 확인해 줍니다. 이 과정 역시 $O( \sqrt{N} )$에 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#include <cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<math.h>
#include<string.h>
using namespace std;
ll b[100],d[3000000],dcnt=0;
int main() {
    ll n, i;
    scanf("%lld", &n);
    if (n == 2) {
        printf("*");
        return 0;
    }
    for (i = 2;i <= n;i++) {
        ll cnt = 0,ii=n;
        while (ii != 0) {
            cnt++;
            b[cnt] = ii % i;
            ii /= i;
        }
        if (cnt == 2) break;
        ll s = 1, e = cnt;
        while (s < e) {
            if (b[s] != b[e]) break;
            s++; e--;
        }
        if (s >= e) {
            dcnt++;
            d[dcnt] = i;
        }
    }
    ll tmp = sqrt(n);
    for (i = 1;i<=tmp;i++) {
        if (i * i == n) break;
        if ((n - i) % i == 0) {
            if ((n - i) / i <= i) break;
            dcnt++;
            d[dcnt] = (n - i) / i;
        }
    }
    sort(d, d + dcnt+1);
    for (i = 1;i <= dcnt;i++) printf("%lld ", d[i]);
    return 0;
}