4259. 제곱수의 합 계산하기(D4)

 long long으로 해결할 수 없다고 댓글에 달려있어서

vector를 이용하여 , 숫자를 문자열 곱셈으로 답을 구했다.

normalize, multiply는 곱셈에 관련된 함수로, 주어진 a^b을 수행한다 즉 a * a * a ...를 이용해 곱셈 답을 찾아내고

그 이후에 계산한 값들을 다 더해준다.

#include <memory.h>
#include <stdio.h>
#include <vector>
#include <stdlib.h>
using namespace std;
void normalize(vector<int>& num)
{
    num.push_back(0);
 
    for (int i = 0; i < num.size() - 1; i++)
    {
        if (num[i] < 0)
        {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i + 1] -= borrow;
            num[i] += borrow * 10;
        }
        else
        {
            num[i + 1] += num[i] / 10;
            num[i] %= 10;
        }
    }
    while (num.size() > 1 && num.back() == 0)
        num.pop_back();
}
 
vector<int> multiply(const vector<int>& a, const vector<int>& b)
{
    vector<int> c(a.size() + b.size() + 1, 0);
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < b.size(); j++)
        {
            c[i + j] += a[i] * b[j];
        }
    }
    normalize(c);
    return c;
}
 
int main()
{
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        int n;
        scanf("%d", &n);
        int size = 0;
        vector< vector<int> > v;
        vector< vector<int> > ans;
        for (int i = 0; i < n; i++)
        {
            vector<int> vt;
            vector<int> vt2;
            vt.push_back(1);
            ans.push_back(vt);
            v.push_back(vt2);
        }
        for (int i = 0; i < n; i++)
        {
            int t;
            scanf("%d", &t);
            int temp1 = t / 10;
            int temp2 = t % 10;
            while (temp1 != 0)
            {
                v[i].push_back(temp1 % 10);
                temp1 /= 10;
            }
            for (int j = 0; j < temp2; j++)
            {
                ans[i] = multiply(ans[i], v[i]);
            }
            if(ans[i].size() > size)
                size = ans[i].size();
        }
        for (int i = 0; i < n; i++)
            ans[i].resize(size);
        int flag = 0;
        vector<int> result;
        for (int i = 0; i < size; i++)
        {
            int temp = flag;
            flag = 0;
            for (int j = 0; j < n; j++)
            {
                temp += ans[j][i];
            }
            if (temp >= 10)
            {
                flag = temp / 10;
                result.push_back(temp % 10);
            }
            else
            {
                result.push_back(temp);
            }
        }
        if(flag!=0)
            result.push_back(flag);
        printf("#%d ", test_case);
        for (int i = result.size() - 1; i >= 0; i--)
            printf("%d", result[i]);
        printf("\n");
    }
    return 0;
}