취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2731번 문제인 1379와 세제곱이다.
문제는 아래 링크를 확인하자.

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

먼저 길이가 n이고 1,3,7 또는 9로 끝나는 양의 정수 s에 대하여 s보다 길이가 짧거나 같은 양의 정수 중 세제곱의 마지막 n자리가 s와 같은 정수가 유일함을 수학적 귀납법을 이용해 간단히 살펴보자. 이 과정을 따라가면 그러한 정수를 구하는 방법을 알 수 있다.

n=1인 경우 s가 1, 3, 7, 9일 경우 각각 1, 7, 3, 9와 같이 세제곱하면 1의 자리가 s가 되는 한 자리 정수가 존재함을 알 수 있다.

n이 k 미만일 때 모든 길이가 n이고 1,3,7 또는 9로 끝나는 양의 정수 s에 대하여 s보다 길이가 짧거나 같고 세제곱의 마지막 n자리가 s와 같은 양의 정수를 유일하게 찾을 수 있다고 가정하자.

k자리 정수 s에 대하여 세제곱이 s의 마지막 k-1자리와 겹치는 마지막 자리를 갖는 유일한 k-1자리 수(leading zero 포함)를 tmp라 하자. 우리가 찾는 수는 tmp로 끝나야 한다는 사실은 자명하다.

이제 우리가 구하는 수의 k번째 자리 수를 x라 했을 때, \((10^{k - 1} x + tmp)^3\)의 전개식과 s의 마지막 k자리를 비교하면 어렵지 않게 x의 값이 유일함을 증명할 수 있다. 그리고 그 값 또한 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

int T; ll N;
int num[11], ans[10], dgt;
int inv[10] = {0, 1, 0, 7, 0, 0, 0, 3, 0, 9};

void solve() {
    memset(ans, 0, sizeof(ans));
    memset(num, 0, sizeof(num));
    dgt = 0;
    cin >> N;
    
    if (N % 10 == 1) {
        num[0] = 1;
        ans[0] = 1;
    }
    else if (N % 10 == 3) {
        num[0] = 3, num[1] = 4, num[2] = 3;
        ans[0] = 7;
    }
    else if (N % 10 == 7) {
        num[0] = 7, num[1] = 2;
        ans[0] = 3;
    }
    else{
        num[0] = 9, num[1] = 2, num[2] = 7;
        ans[0] = 9;
    }
    
    dgt++, N /= 10;
    
    while (N) {
        int tmp = 0;
        for (int i = 0; i < dgt; i++){
            for (int j = 0; j < dgt; j++){
                for (int k = 0; k < dgt; k++){
                    if (i + j + k == dgt) tmp += ans[i] * ans[j] * ans[k];
                }
            }
        }
        int d = dgt;
        while (tmp && d < 10){
            num[d] += tmp % 10;
            if (num[d] > 9){
                num[d + 1] += num[d]/10;
                num[d] %= 10;
            }
            
            tmp /= 10, d++;
        }
        
        int x = N % 10 - num[dgt];
        if (x < 0) x += 10;
        ans[dgt] = (x * inv[ans[0]] * inv[ans[0]] * inv[3]) % 10;
        
        tmp = ans[dgt] * ans[0] * ans[0] * 3;
        d = dgt;
        while (tmp && d < 10){
            num[d] += tmp % 10;
            if (num[d] > 9){
                num[d + 1] += num[d] / 10;
                num[d] %= 10;
            }
            
            tmp /= 10, d++;
        }
        
        dgt++, N /= 10;
    }
    
    int i = dgt - 1;
    
    while (!ans[i]) i--;
    for (; i > -1; i--) cout << ans[i];
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> T;
    while (T--) solve();
}