// HappyTickets.cpp : Defines the entry point for the console application.
//

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

#define MIN_POW (1+1)
#define SHIFT '0'


//выделение len Байт
char* allocate_memory(size_t len)
{
	return (char*)malloc(len*sizeof(char));
}

//освобождение памяти
int freeMemory(char* s1, char* s2, int isFreeMemory)
{
	if (isFreeMemory >= 1)
	{
		free(s1);
		s1 = NULL;
	}
	if (isFreeMemory >= 2)
	{
		free(s2);
		s2 = NULL;
	}
	return 0;
}



//СУММА
//s1>=s2
int la_sum_inplace(char* sum, size_t p, char* s1, size_t p1, char* s2, size_t p2)
{
	memset(sum, '0', p); *(sum + p - 1) = '\0';//установка стартового значения
	memcpy(sum + p1 - p2 + 1, s2, p2 - 1);//пишем в конец результирующей строки минимальное число
	int d = 0;
	for (int i = p - 2; i > 0; i--)
	{
		int t0 = *(sum + i) + *(s1 + i - 1) + d - 2 * SHIFT;
		int t1 = t0 % 10;
		*(sum + i) = t1 + '0';
		d = (t0 >= 10) ? 1 : 0;
	}
	if (!d && p != 2)
		memmove(sum, sum + 1, p - 1);
	else
		*(sum + 0) = d + '0';
	return 0;
}

//s1+s2      s1,s2>=0
char* la_sum(char* s1, char* s2, int isFreeMemory)
{
	size_t p[2] = { strlen(s1) + 1, strlen(s2) + 1 };
	int max_i = (p[0] > p[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	char* max_s = (max_i == 0) ? s1 : s2;
	char* min_s = (min_i == 0) ? s1 : s2;

	int p_res = p[max_i] + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	char* res = allocate_memory(p_res);
	la_sum_inplace(res, p_res, max_s, p[max_i], min_s, p[min_i]);   // calculate in-place   
	freeMemory(s1, s2, isFreeMemory);
	return res;
}




//УМНОЖЕНИЕ 
//s-строка,num-число
//функция оптимизированна под умножение строки на строку за счёт сдвига shift
int la_mul_string_on_num_inplace(char* res, size_t p, char* s, size_t ps, unsigned int num, int sh)
{
	if ((ps == MIN_POW && s[0] == '0') || (num == 0))
	{
		res[0] = '0'; res[1] = '\0';
		return 0;
	}
	memset(res, '0', p);
	int d = 0;
	for (int i = ps - 2; i >= 0; --i)
	{
		int t = (s[i] - SHIFT)*num + d;
		int t1 = t % 10;
		res[i + 1] = t1 + SHIFT;
		d = (t - t1) / 10;
	}
	res[p - 1] = '\0';
	if (!d)
		memmove(res, res + 1, p - 1);
	else
		res[0] = d + SHIFT;
	return 0;
}

//s*num*10^sh
char* la_mul_string_on_num(char* s, unsigned int num, int sh)
{
	size_t ps = strlen(s) + 1;
	size_t p = ps + 1 + sh;//реализую умножение на 10^sh
	char* res = allocate_memory(p);
	la_mul_string_on_num_inplace(res, p, s, ps, num, sh);
	return res;
}


//s1*s2
char* la_mul(char* s1, char* s2, int isFreeMemory)
{
	size_t p1 = strlen(s1) + 1;
	size_t p2 = strlen(s2) + 1;
	size_t p = p1 + p2 - 1;

	char* res = allocate_memory(2); res[0] = '0'; res[1] = '\0';
	for (int i = p2 - 2; i >= 0; --i)
	{
		char* t = la_mul_string_on_num(s1, s2[i] - SHIFT, p2 - 2 - i);
		res = la_sum(res, t, 2);
	}
	freeMemory(s1, s2, isFreeMemory);
	return res;
}


//РАЗНОСТЬ s1-s2 s1>=s2
int la_diff_inplace(char* res, size_t p, const char* s1, size_t p1, const char* s2, size_t p2)
{
	memcpy(res, s1, p);
	for (int i = p - 2; i >= 0; --i)
	{
		if (res[i] - s2[i] >= 0)
		{
			res[i] = res[i] - s2[i] + SHIFT;
		}
		else
		{
			int j;
			for (j = i - 1; res[j] == '0'; --j)
			{
				res[j] = '9';
			}
			res[j] -= 1;
			res[i] = 10 + res[i] - s2[i] + SHIFT;

		}
	}
	int count_0 = 0;
	int z = 0;
	for (; z < p - 1 && res[z] == '0'; ++z);
	if (z)
		memmove(res, res + z, p - z);
	return 0;
}

char* la_diff(char* s1, char* s2, int isFreeMemory)
{
	size_t p1 = strlen(s1) + 1;
	size_t p2 = strlen(s2) + 1;
	size_t p = p1;

	char* ss2 = (char*)malloc(sizeof(char)*p);
	memset(ss2, '0', p);
	memcpy(ss2 + p - p2, s2, p2);//было memcpy(ss2 + p - p2, s2, p2);

	char* res = allocate_memory(p);
	la_diff_inplace(res, p, s1, p, ss2, p);
	free(ss2);
	freeMemory(s1, s2, isFreeMemory);
	return res;
}





struct Number
{
	int num;
	int num2;
	int count;
	int* multipliers;
};

struct Number* initializeNumber(int a)
{
	struct Number* n = (struct Number*)malloc(sizeof(struct Number));
	n->num = a;
	n->num2 = a;
	n->count = 0;
	n->multipliers = NULL;
	return n;
}

int viewNumber(struct Number* a)
{
	printf("num= %i\n", a->num);
	printf("num2= %i\n", a->num2);
	printf("divisors:");
	for (int i = 0; i < a->count; ++i)
	{
		printf("%i ", a->multipliers[i]);
	}
	printf("\n");
	return 0;
}

//assume a->num > 1
int factorization(struct Number* a)
{
	for (int i = 2; i <= a->num2; ++i)
	{
		if (a->num2%i == 0)
		{
			a->count += 1;
			a->multipliers = (int*)realloc(a->multipliers, a->count*sizeof(int));
			a->multipliers[a->count - 1] = i;

			a->num2 /= i;
			factorization(a);
			break;
		}
	}
	return 0;
}
//Сочетания
char* la_combination(unsigned n, unsigned m)
{
	char* res = allocate_memory(2); res[0] = '1'; res[1] = '\0';
	m = (n - m > m) ? m : n - m;
	if (m == 0)
	{
		return res;
	}
	int* up = (int*)malloc(sizeof(int)*m);//числитель
	int* down = (int*)malloc(sizeof(int)*m);//знаменатель

	for (int i = 1; i <= m; ++i)
	{
		*(up + m - i) = n - m + i;
		*(down + m - i) = i;
	}

	int len_down = m;
	for (int i = 0; i < len_down; ++i)//1 проход по знаменателю, длина знаменателя меняется
	{
		int j = 0;
		for (j = 0; j < m; ++j)//проход по числителю
		{
			if (!(up[j] % down[i]))
			{
				up[j] /= down[i];
				break;
			}
		}
		if (j == m && down[i] != 1) //если перебрали все элементы числителя, а фиксированный элемент знаменателя не сократили
		{
			struct Number* n = initializeNumber(down[i]);
			factorization(n); //раскладываю число на множители
			down[i] = 1;
			len_down += n->count;
			down = (int*)realloc(down, sizeof(int)*len_down);
			for (int i = 0; i < n->count; ++i)
			{
				down[len_down - n->count + i] = n->multipliers[i];
			}
			free(n->multipliers);
			free(n);
		}
	}

	char* t = (char*)malloc(10);
	for (int i = 0; i < m; ++i)
	{
		sprintf(t, "%d", up[i]);
		res = la_mul(res, t, 1);
	}
	free(t);
	free(up);
	free(down);
	return res;
}