#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *makeLong (char *a){
    char *res = malloc(256);
    memset(res, 0, 256);
    for (size_t i = 0, len = strlen(a); i < len; i++){
        res[i] = a[len - i - 1] - '0';
    }
    return res;
}

char *makeString (char *a){
    size_t size = 256;
    for (; size > 1 && a[size - 1] == 0; size--){}
    char *res = malloc(size + 1);
    res[size] = 0;
    for (size_t i = 0; i < size; i++){
        res[i] = a[size - i - 1] + '0';
    }
    return res;
}

void sum (char *a, char *b){
    for (size_t i = 0; i < 256; i++){
        a[i] += b[i];
        i < 255 ? a[i + 1] += a[i] / 10 : 0;
        a[i] %= 10;
    }
}

void sub (char *a, char *b){
    for (size_t i = 0; i < 256; i++){
        a[i] -= b[i];
        a[i] < 0 ? a[i] += 10, i < 255 ? a[i + 1]-- : 0 : 0;
    }
}

void mul (char *a, char *b){
    int temp[256] = {0};
    for (size_t i = 0; i < 256; i++){
        for (size_t j = 0; j < 256; j++){
            i + j < 256 ? temp[i + j] += a[i] * b[j] : 0;
        }
    }
    for (size_t i = 0; i < 256; i++){
        i < 255 ? temp[i + 1] += temp[i] / 10 : 0;
        temp[i] %= 10;
        a[i] = temp[i];
    }
}

void sdiv (char *a, char b){
    if (b < 1 || b > 9){
        return;
    }
    char temp[256] = {0};
    for (size_t i = 0; i < 256; i++){
        char t = temp[255 - i] * 10 + a[255 - i];
        temp[255 - i] = t / b;
        i < 255 ? temp[255 - i - 1] = t % b : 0;
    }
    memcpy(a, temp, 256);
}

int less (char *a, char *b){
    for (size_t i = 0; i < 256; i++){
        if (a[255 - i] < b[255 - i]){
            return 1;
        }
        if (a[255 - i] > b[255 - i]){
            return 0;
        }
    }
    return 0;
}

char **divide_strings (char *a, char *b){
    char **res = malloc(sizeof(char *) * 2);
    char *la = makeLong(a);
    char *lb = makeLong(b);
    if (less(la, lb)){
        res[0] = makeString(makeLong("0"));
        res[1] = makeString(la);
        free(la);
        free(lb);
        //printf("quot = %s\nrem = %s\n", res[0], res[1]);
        return res;
    }
    char *buf = malloc(256 * 4);
    char *left = buf;
    memset(left, 0, 256);
    char *right = buf + 256;
    memcpy(right, la, 256);
    char *middle = buf + 256 * 2;
    memcpy(middle, la, 256);
    sdiv(middle, 2);
    char *temp = buf + 256 * 3;

    while (1){
        memcpy(temp, middle, 256);
        mul(temp, lb);
        if (!less(la, temp)){
            sum(temp, lb);
            if (less(la, temp)){
                sub(temp, lb);
                sub(la, temp);
                break;
            }
            else{
                //printf("small\n");
                memcpy(temp, left, 256);
                sum(temp, middle);
                sdiv(temp, 2);
                memcpy(left, temp, 256);
            }
        }
        else{
            //printf("big\n");
            memcpy(temp, right, 256);
            sum(temp, middle);
            sdiv(temp, 2);
            memcpy(right, temp, 256);
        }
        memcpy(middle, right, 256);
        sum(middle, left);
        sdiv(middle, 2);
    }

    res[0] = makeString(middle);
    res[1] = makeString(la);
    free(la);
    free(lb);
    free(buf);
    //printf("quot = %s\nrem = %s\n", res[0], res[1]);
    return res;
}

int main (int argc, char **argv){
    // char *foo = makeLong("987654321987654321987654321987654321");
    // char *baz = makeLong("987654321");
    // sdiv(foo, 2);
    // char *bar = makeString(foo);
    // printf("%s\n", bar);
    // free(foo);
    // free(bar);
    // free(baz);

    divide_strings("729", "9");
}