//https://www.facebook.com/pages/C%C3%B9ng-h%E1%BB%8Dc-l%E1%BA%ADp-tr%C3%ACnh/632038696941833
#include <iostream>
#include <conio.h>
using namespace std;
struct Node
{
	int x;
	Node *pNext;
};
struct List
{
	Node *pHead, *pTail;
};
void CreateList(List &L)
{
	L.pHead = L.pTail = NULL;
}
Node* CreateNode(int x)
{
	Node *p = new Node;
	if (p == NULL) exit(1);
	p->x = x;
	p->pNext = NULL;
	return p;
}
void AddHead(List &L, Node *p)
{
	if (L.pHead == NULL)
	{
		L.pHead = L.pTail = p;
	}
	else
	{
		p->pNext = L.pHead;
		L.pHead = p;
	}
}
void DelHead(List &L)
{
	Node *p;
	if (L.pHead == NULL) return;
	p = L.pHead;
	L.pHead = p->pNext;
	delete p;
	if (L.pHead == NULL) L.pTail = NULL;
}
void DelTail(List &L)
{
	Node *p = L.pHead;
	Node *pBef = NULL;
	if (p == NULL) return;
	if (L.pHead == L.pTail)
	{
		L.pHead = L.pTail = NULL;
		delete p;
		return;
	}
	while (p != L.pTail)
	{
		pBef = p;
		p = p->pNext;
	}
	pBef->pNext = NULL;
	L.pTail = pBef;
}
void Input(List &L)
{
	int x;
	Node *p = NULL;
	cout << endl;
	cout << "nhap so nguyen: ";
	do
	{
		x = getch();
		if (x >= 48 && x <= 57)
		{
			x = x - 48;
			cout << x;
			p = CreateNode(x);
			AddHead(L, p);
		}
		else
		{
			if (x == 8)
			{
				if (L.pHead != NULL)
				{
					p = L.pHead;
					L.pHead = L.pHead->pNext;
					delete p;
					putch(8);
					putch(' ');
					putch(8);
				}
			}
		}
	} while (x != 13);
}
void Output(List &L)
{
	Node *p = L.pHead;
	while (p != NULL)
	{
		cout << p->x;
		p = p->pNext;
	}
}
void AddTail(List &L, Node *p)
{
	if (L.pHead == NULL)
	{
		L.pHead = L.pTail = p;
	}
	else
	{
		L.pTail->pNext = p;
		L.pTail = p;
	}
}
int ListLen(List L)
{
	int dem = 0;
	Node *p = L.pHead;
	while (p != NULL)
	{
		dem++;
		p = p->pNext;
	}
	return dem;
}
int SoSanhListCungDoDai(Node *p1, Node *p2)
{
	int t;
	if (p1->pNext != NULL && p2->pNext != NULL)
	{
		t = SoSanhListCungDoDai(p1->pNext, p2->pNext);
		if (t != 0) return t;
	}
	if ((p1->pNext == NULL && p2->pNext == NULL) || t == 0)
	{
		if (p1->x > p2->x) return 1;
		if (p1->x < p2->x) return -1;
		return 0;
	}
}
int SoSanhList(List L1, List L2)
{
	int len1 = ListLen(L1), len2 = ListLen(L2);
	if (len1 > len2) return 1;
	if (len1 == len2) return SoSanhListCungDoDai(L1.pHead, L2.pHead);
	if (len1 < len2) return -1;
}
void CongList(List L1, List L2, List &L3)
{
	Node *p1 = L1.pHead, *p2 = L2.pHead;
	Node *p3 = NULL;
	int r = 0;
	int x;
	while (p1 != NULL && p2 != NULL)
	{
		x = p1->x + p2->x + r;
		if (x >= 10)
		{
			r = 1;
			x = x - 10;
		}
		else
			r = 0;
		p3 = CreateNode(x);
		AddHead(L3, p3);
		p1 = p1->pNext;
		p2 = p2->pNext;
	}
	while (p1 != NULL)
	{
		x = p1->x + r;
		if (x >= 10)
		{
			r = 1;
			x = x - 10;
		}
		else
			r = 0;
		p3 = CreateNode(x);
		AddHead(L3, p3);
		p1 = p1->pNext;
	}
	while (p2 != NULL)
	{
		x = p2->x + r;
		if (x >= 10)
		{
			r = 1;
			x = x - 10;
		}
		else
			r = 0;
		p3 = CreateNode(x);
		AddHead(L3, p3);
		p2 = p2->pNext;
	}
	if (r == 1)
	{
		p3 = CreateNode(1);
		AddHead(L3, p3);
	}
}
void TruList(List L1, List L2, List &L3)
{
	List L;
	int dau = 1;
	if (SoSanhList(L1, L2) == -1)
	{
		L.pHead = L1.pHead;
		L1.pHead = L2.pHead;
		L2.pHead = L.pHead;
		dau = -1;

	}
	Node *p1 = L1.pHead, *p2 = L2.pHead, *p3 = NULL;
	int r = 0, x;
	while (p1 != NULL && p2 != NULL)
	{
		x = p1->x - p2->x - r;
		if (x < 0)
		{
			r = 1;
			x = x + 10;
		}
		else
			r = 0;
		p3 = CreateNode(x);
		AddHead(L3, p3);

		p1 = p1->pNext;
		p2 = p2->pNext;
	}
	while (p1 != NULL)
	{
		x = p1->x - r;
		if (x < 0)
		{
			r = 1;
			x = x + 10;
		}
		else
			r = 0;
		p3 = CreateNode(x);
		AddHead(L3, p3);
		p1 = p1->pNext;
	}
	p3 = L3.pHead;
	while (L3.pHead != NULL)
	{
		if (L3.pHead->x == 0)
		{
			p2 = L3.pHead;
			L3.pHead = L3.pHead->pNext;
			delete p2;
			if (ListLen(L3) == 1)
			{
				if (L3.pHead->x == 0) dau = 0;
				break;
			}
		}
		else
			break;
	}
	if (L3.pHead) L3.pHead->x *= dau;
	else
		CreateList(L3);
}
void Chen(List &L)
{
	AddHead(L, CreateNode(0));
}
void HuyList(List &L1)
{
	Node *p1 = L1.pHead;
	while (L1.pHead != NULL)
	{
		L1.pHead = L1.pHead->pNext;
		delete p1;
		p1 = L1.pHead;
	}
	L1.pTail = NULL;
}
void CopyList(List L, List &L1)
{

	Node *p = L.pHead;
	while (p != NULL)
	{
		AddHead(L1, CreateNode(p->x));
		p = p->pNext;
	}
}
void NhanListVoiMotSo(List L, List &L1, int x)
{
	Node *p = L.pHead;
	int r = 0;
	int n;
	while (p != NULL)
	{
		n = p->x * x + r;
		if (n >= 10)
		{
			r = n / 10;
			n %= 10;
		}
		else
			r = 0;
		AddTail(L1, CreateNode(n));
		p = p->pNext;
	}

	if (r != 0)
	{
		AddTail(L1, CreateNode(r));
	}
}
void DaoList(List &L)
{
	Node *p1 = L.pHead;
	List L1;
	CreateList(L1);
	while (p1 != NULL)
	{
		AddHead(L1, CreateNode(p1->x));
		p1 = p1->pNext;
	}
	HuyList(L);
	L.pHead = L1.pHead;
	L.pTail = L1.pTail;
	CreateList(L1);
}
void NhanList(List L1, List L2, List &L3)
{
	Node *p1 = L1.pHead, *p2 = L2.pHead, *p3 = NULL;
	int x = 0;
	int r = 0;
	int dem = 0;
	List L, L4;
	CreateList(L);
	CreateList(L4);
	while (p2 != NULL)
	{
		NhanListVoiMotSo(L1, L, p2->x);
		for (int i = 0; i < dem; i++) Chen(L);

		CongList(L, L3, L4);
		HuyList(L);
		HuyList(L3);
		CopyList(L4, L3);
		HuyList(L4);
		p2 = p2->pNext;
		dem++;
	}
	DaoList(L3);
}
int CopyListNode(List &L, Node *&p, int n)
{
	int i = 0;
	while (p && i < n)
	{
		AddHead(L, CreateNode(p->x));
		p = p->pNext;
		i++;
	}
	if (i < n) return 0;
	return 1;
}
int SoSanhListXuoi(List L1, List L2)
{
	int len1 = ListLen(L1);
	int len2 = ListLen(L2);
	if (len1 > len2) return 1;
	if (len1 < len2) return -1;
	Node *p1 = L1.pHead;
	Node *p2 = L2.pHead;
	while (p1 && p2)
	{
		if (p1->x > p2->x) return 1;
		if (p1->x < p2->x) return -1;
		p1 = p1->pNext;
		p2 = p2->pNext;
	}
	if (p1 == NULL && p2) return -1;
	if (p1 && p2 == NULL) return 1;
	return 0;
}

void ChiaListLay1So(List L1, List L2, int &KetQua)
{
	//L1, L2 la list nguoc
	int t;
	List Tam;
	CreateList(Tam);
	List L;
	CreateList(L);
	CopyList(L2, L);
	List L3;
	CreateList(L3);
	CopyList(L1, L3);
	//Tam, L va L3 la list xuoi
	while (L3.pHead != NULL && L3.pHead->x == 0) DelHead(L3);
	DaoList(L);
	for (int i = 1; i <= 10; i++)
	{
		//dua vao list nguoc, tra ve list nguoc
		NhanListVoiMotSo(L, Tam, i);
		DaoList(Tam);
		t = SoSanhListXuoi(L3, Tam);
		if (t <= 0)
		{
			if (t == 0)
			{
				KetQua = i;
			}
			else
				KetQua = i - 1;
			return;
		}
		else
			HuyList(Tam);
	}
}
void ChiaList(List L1, List &L2, List &L3)
{
	//L1, L2 list nguoc
	int len = ListLen(L2);
	List Tam;
	CreateList(Tam);
	List L4;
	CreateList(L4);
	List L5;
	CreateList(L5);
	DaoList(L1);//L1 list xuoi
	Node *p1 = L1.pHead;
	int t = CopyListNode(Tam, p1, len);//list xuoi
	if (t == 0)
	{
		AddHead(L3, CreateNode(0));
		return;
	}
	//l2 list nguoc
	//tam là list nguoc
	while (1)
	{

		ChiaListLay1So(Tam, L2, t);
		NhanListVoiMotSo(L2, L4, t);//list cung chieu
		if (t)
		{
			while (L4.pHead != L4.pTail && L4.pTail->x == 0)
				DelTail(L4);
			TruList(Tam, L4, L5);
			//L5 xuoi
			if (L5.pHead && L5.pHead->x == 0)
			{
				HuyList(Tam);
				HuyList(L5);
			}
			else
			if (L5.pHead && L5.pHead->x > 0)
			{
				Tam.pHead = L5.pHead;
				Tam.pTail = L5.pTail;
				CreateList(L5);
			}
			DaoList(Tam);
		}
		HuyList(L4);
		AddTail(L3, CreateNode(t));
		if (p1 == NULL) break;
		AddHead(Tam, CreateNode(p1->x));
		p1 = p1->pNext;
	}
	DaoList(L2);
	if (L3.pHead->x == 0) DelHead(L3);
}



void main()
{
	system("start https://www.facebook.com/pages/C%C3%B9ng-h%E1%BB%8Dc-l%E1%BA%ADp-tr%C3%ACnh/632038696941833");
	List L1, L2, L3, L4;
	int dau;
	CreateList(L1);
	CreateList(L2);
	CreateList(L3);
	Input(L1);
	Input(L2);
	CongList(L1, L2, L3);
	cout << endl;
	cout << "Cong: ";
	Output(L3);
	HuyList(L3);
	TruList(L1, L2, L3);
	cout << endl;
	cout << "Tru: ";
	Output(L3);
	HuyList(L3);
	NhanList(L1, L2, L3);
	cout << endl;
	cout << "Nhan: ";
	Output(L3);
	HuyList(L3);
	ChiaList(L1, L2, L3);
	cout << endl;
	cout << "Chia: ";
	Output(L3);
	getchar();
}