AOJ 0287 - Jinkoki

多倍長書くだけ．

最初に

以下の文字列をコピペするといいかも．(問題文からコピペできるといいなあ)

const std::string units[] = {
    "", "Man", "Oku", "Cho", "Kei", "Gai", "Jo",
    "Jou", "Ko", "Kan", "Sei", "Sai", "Gok", "Ggs",
    "Asg", "Nyt", "Fks", "Mts"
};

解法

多倍長書いてゴニョゴニョする．

コード

#include <cstdio>
#include <cstring>
#include <iostream>

const int MAX_D = 400;

struct Integer{
    Integer(int i = 0){
        memset(digits, 0, sizeof(digits));
        n = 0;
        
        while(i > 0){
            digits[n++] = i % 10;
            i /= 10;
        }
    }
    Integer(const std::string& s){
        memset(digits, 0, sizeof(digits));
        n = 0;
        
        bool f = false;
        for(int j=(int)s.size()-1;j>=0;j--){
            if(!std::isdigit(s[j])){continue;}
            
            if(s[j] != '0'){
                digits[n++] = s[j] - '0';
                f = true;
            }else if(f){
                digits[n++] = s[j] - '0';
            }
        }
    }
    int digits[MAX_D], n;
};

Integer operator*(const Integer& lhs, const Integer& rhs){
    Integer res;
    for(int i=0;i<MAX_D;i++){
        for(int j=0;j<MAX_D;j++){
            if(i + j >= MAX_D){continue;}
            int x = lhs.digits[i] * rhs.digits[j] + res.digits[i+j];
            res.digits[i+j] = x % 10;
            if(i + j + 1 < MAX_D){
                res.digits[i+j+1] += x / 10;
            }
        }
    }
    
    return res;
}

Integer operator+(const Integer& lhs, const Integer& rhs){
    Integer res;
    for(int i=0;i<MAX_D;i++){
        int x = lhs.digits[i] + rhs.digits[i] + res.digits[i];
        res.digits[i] = x % 10;
        if(i+1 < MAX_D){
            res.digits[i+1] = x / 10;
        }
    }
    
    return res;
}

int main(){
    int M, N;
    while(scanf("%d %d", &M, &N), M || N){
        Integer num(1), a(M);
        while(N > 0){
            if(N & 1){num = num * a;}
            a = a * a;
            N >>= 1;
        }

        int mx;
        bool f = false;
        for(int i=MAX_D-1;i>=0;i--){
            if(num.digits[i] != 0){f = true;}

            if(f){
                mx = i;
                break;
            }        
        }
        
        std::string S = "";
        for(int i=mx;i>=0;){
            int x = 0;
            while(true){
                x = x * 10 + num.digits[i];
                if(i % 4 == 0){break;}
                i--;
            }
            if(x > 0){
                S += std::to_string(x) + units[i/4];
            }
            i--;
        }

        std::cout << S << std::endl;
    }
}