SMMR-033: Power Mod (Level God)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
using v_char = vector <char>;

void pv(v_char v){ // check vector
    for(auto i: v) printf("%c", i);
    printf("\n");
}

v_char multiplication(v_char num1, v_char num2){
    v_char digit[50];
    int sz1 = num1.size();
    int idx = 1;
    for(int i=sz1-1;i>=0;i--){
        int r = 0;
        for(int j=1;j<idx;j++) digit[idx].push_back('0');
        int n = (num1[i] - '0');
        int sz2 = num2.size();
        for(int j=sz2-1;j>=0;j--){
            int dg = num2[j] - '0';
            int m = dg * n + r;
            digit[idx].push_back((m%10) + '0');
            r = m/10;
        }
        if(r > 0) digit[idx].push_back(r + '0');
        idx ++;
    }
    v_char ans(digit[idx-1].size()+1, '0');
    for(int j=0;j<digit[1].size();j++) ans[j] = digit[1][j];
    for(int i=2;i<idx;i++){
        int sz = digit[i].size();
        int r = 0;
        for(int j=0;j<sz;j++){
            int dg = digit[i][j] - '0';
            int n = ans[j] - '0';
            int m = dg + n + r;
            ans[j] = (m%10) + '0';
            r = m/10;
        }
        ans[sz] += r;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int find_digit(lli num){
    int digit = 0;
    while(num > 0){
        num = num / 10;
        digit ++;
    }
    return digit;
}

lli find_number(int l, int r, v_char v){
    lli num = 0;
    for(int i=l;i<=r;i++){
        num = num * 10 + v[i] - '0';
    }
    return num;
}

v_char modulo(v_char num, lli mod){
    int dg = find_digit(mod);
    if(num.size() < dg) return num;
    lli r = find_number(0, dg-1, num) % mod;
    for(int i=dg;i<num.size();i++){
        r = 10*r + num[i] - '0';
        r = r % mod;
    }

    v_char ans;
    if(r == 0) ans.push_back('0');
    while(r > 0){
        ans.push_back((r%10) + '0');
        r = r / 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

v_char f(v_char n, lli k, lli m){
    if(k == 0){
        v_char ans {'1'};
        return ans;
    }
    if(k == 1)
        return n;
    v_char Mod = f(n, k/2, m);
    Mod = modulo( multiplication(Mod, Mod), m);
    if(k % 2 == 0) {
        return Mod;
    }
    v_char multi = multiplication(Mod, n);
    Mod = modulo( multi, m);
    return Mod;
}

int main(){

    lli n, k, m;
    scanf("%lld%lld%lld", &n, &k, &m);

    v_char num;
    while(n > 0){
        num.push_back((n%10) + '0');
        n = n / 10;
    }
    reverse(num.begin(), num.end());

    v_char ans = f(modulo(num, m), k, m);

    for(auto a: ans) printf("%c", a);

    return 0;
}