From 2a7bc10f6c011d19fb3b0e73068f7e1a9c30ace0 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Sat, 8 Oct 2016 09:56:43 +0700
Subject: Initial commit

---
 NTU/root.c | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
 create mode 100644 NTU/root.c

(limited to 'NTU/root.c')

diff --git a/NTU/root.c b/NTU/root.c
new file mode 100644
index 0000000..01b9b30
--- /dev/null
+++ b/NTU/root.c
@@ -0,0 +1,37 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+int cmp(const void *x, const void *y)
+{
+	return *(long *) x - *(long *) y;
+}
+
+int main()
+{
+	short i;
+	long a[31622]; /* square root of 1 billion */
+	for (i = 0; i < 31622; i++) {
+		a[i] = i + 1;
+		a[i] *= a[i];
+	}
+
+	short t;
+	scanf("%hd", &t);
+
+	long *n = malloc(t * sizeof(long));
+	for (i = 0; i < t; i++)
+		scanf("%ld", &n[i]);
+
+	long foo;
+	for (i = 0; i < t; i++) {
+		foo = (long) sqrt(n[i]);
+		foo *= foo;
+		foo = (long *) bsearch(&foo, a, 31622, 4, cmp) - a;
+		while ((foo > 0) && (n[i] % a[foo]))
+			foo--;
+		printf("%hd %ld\n", foo + 1, n[i] / a[foo]);
+	}
+
+	return 0;
+}
-- 
cgit 1.4.1