From 250b7d75204bb18311f51d8b67164f9ad4cef9f2 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Sun, 30 Oct 2016 16:37:10 +0700
Subject: NTU: Add luth2.c and TutOnEqua.c

---
 NTU/README.md   |  3 ++-
 NTU/TutOnEqua.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 NTU/luth2.c     | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 112 insertions(+), 1 deletion(-)
 create mode 100644 NTU/TutOnEqua.c
 create mode 100644 NTU/luth2.c

(limited to 'NTU')

diff --git a/NTU/README.md b/NTU/README.md
index 345342e..8261d6c 100644
--- a/NTU/README.md
+++ b/NTU/README.md
@@ -3,7 +3,7 @@
 - [x] pali: [Số Palindrome](http://laptrinh.ntu.edu.vn/Problem/Details/41)
 - [x] gacho: [Gà và chó](http://laptrinh.ntu.edu.vn/Problem/Details/116)
 - [x] luth: [Lũy thừa](http://laptrinh.ntu.edu.vn/Problem/Details/1156)
-- [ ] luth2: [Lũy thừa 2](http://laptrinh.ntu.edu.vn/Problem/Details/2240)
+- [x] luth2: [Lũy thừa 2](http://laptrinh.ntu.edu.vn/Problem/Details/2240)
 - [x] writer: [Robot đánh chữ](http://laptrinh.ntu.edu.vn/Problem/Details/3255)
 - [x] ngto4: [Tổng nguyên tố](http://laptrinh.ntu.edu.vn/Problem/Details/3256)
 - [x] demso0: [Đếm số không bên phải](http://laptrinh.ntu.edu.vn/Problem/Details/3330)
@@ -27,3 +27,4 @@
 - [x] chenhlech: [Chênh lệch](http://laptrinh.ntu.edu.vn/Problem/Details/5574)
 - [ ] editpic: [Chỉnh sửa ảnh](http://laptrinh.ntu.edu.vn/Problem/Details/5588)
 - [ ] cntpalin: [Đếm số Palindrome](http://laptrinh.ntu.edu.vn/Problem/Details/5600)
+- [x] TutOnEqua: [Tutoring on equations](http://laptrinh.ntu.edu.vn/Problem/Details/5606)
diff --git a/NTU/TutOnEqua.c b/NTU/TutOnEqua.c
new file mode 100644
index 0000000..84cec70
--- /dev/null
+++ b/NTU/TutOnEqua.c
@@ -0,0 +1,55 @@
+#include <stdio.h>
+
+#define abs(x) (x < 0) ? -x : x
+
+int gcd(int a, int b)
+{
+	int c;
+
+	while (b) {
+		c = a % b;
+		a = b;
+		b = c;
+	}
+
+	return a;
+}
+
+int main()
+{
+	int a, b, c, i, j, k, l, m, n, t;
+	char solutions[201][100];
+
+	scanf("%d", &t);
+	for (i = t; i; i--) {
+		for (k = 0; k < 201; k++)
+			for (l = 0; l < 100; l++)
+				solutions[k][l] = 0;
+
+		scanf("%d", &n);
+		for (j = n; j; j--) {
+			scanf("%d %d", &a, &b);
+			if (a) {
+				c = gcd(a, b);
+
+				if (a * b < 0)
+					a = -abs(a / c) + 100;
+				else
+					a = abs(a / c) + 100;
+				b = abs(b / c) - 1;
+
+				solutions[a][b] = 1;
+			}
+		}
+
+		m = 0;
+		for (j = 0; j < 201; j++)
+			for (k = 0; k < 100; k++)
+				if (solutions[j][k])
+					m++;
+
+		printf("%d\n", m);
+	}
+
+	return 0;
+}
diff --git a/NTU/luth2.c b/NTU/luth2.c
new file mode 100644
index 0000000..46bd99a
--- /dev/null
+++ b/NTU/luth2.c
@@ -0,0 +1,55 @@
+#include <stdio.h>
+
+long long modinv(long a, long b)
+{
+	/* From: http://rosettacode.org/wiki/Modular_inverse#C */
+
+	long long t = 0, nt = 1, r = b, nr = a % b, q, tmp;
+
+	while (nr) {
+		q = r / nr;
+
+		tmp = nt;
+		nt = t - q * nt;
+		t = tmp;
+
+		tmp = nr;
+		nr = r - q * nr;
+		r = tmp;
+	}
+
+	return (t < 0) ? t + b : t;
+}
+
+long powmod(long a, long b, long k)
+{
+	if (b == 1)
+		return a;
+
+	long long p = powmod(a, b / 2, k);
+	p = (b % 2) ? p * p * a % k : p * p % k;
+
+	return p;
+}
+
+int main()
+{
+	short t, i;
+	long a, b, k, j;
+	long long c = 1;
+
+	scanf("%hd", &t);
+
+	for (i = t; i; i--) {
+		scanf("%ld %ld %ld", &a, &b, &k);
+
+		if (b < 0) {
+			a = modinv(a, k) % k;
+			b = -b;
+		}
+
+		printf("%ld\n", (b) ? powmod(a, b, k) : 1);
+	}
+
+	return 0;
+}
-- 
cgit 1.4.1