From 235aef5fae393c738e78a5b188051557b6ebd97c Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Mon, 16 Apr 2018 21:15:33 +0800
Subject: 1.6

---
 1.6/numtri.c |  39 +++++++++++++++++++
 1.6/pprime.c | 124 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1.6/sprime.c | 112 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 275 insertions(+)
 create mode 100644 1.6/numtri.c
 create mode 100644 1.6/pprime.c
 create mode 100644 1.6/sprime.c

diff --git a/1.6/numtri.c b/1.6/numtri.c
new file mode 100644
index 0000000..0c62587
--- /dev/null
+++ b/1.6/numtri.c
@@ -0,0 +1,39 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: numtri
+*/
+
+#include <stdio.h>
+
+int main()
+{
+	FILE *fin, *fout;
+	int rows, tri[1000][1000];
+	int i,j;
+
+	fin = fopen("numtri.in", "r");
+	fout = fopen("numtri.out", "w");
+
+	fscanf(fin, "%d", &rows);
+
+	for (i=0; i<rows; i++) {
+		for (j=0; j<=i; j++)
+			fscanf(fin, "%d", &tri[i][j]);
+	}
+
+	fclose(fin);
+
+	for (i=rows-2; i>=0; i--) {
+		for (j=0; j<=i; j++) {
+			if (tri[i+1][j]>tri[i+1][j+1])
+				tri[i][j] += tri[i+1][j];
+			else
+				tri[i][j] += tri[i+1][j+1];
+		}
+	}
+
+	fprintf(fout, "%d\n", tri[0][0]);
+	fclose(fout);
+	return 0;
+}
diff --git a/1.6/pprime.c b/1.6/pprime.c
new file mode 100644
index 0000000..57d930e
--- /dev/null
+++ b/1.6/pprime.c
@@ -0,0 +1,124 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: pprime
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static int sqrmod(int b, int n)
+{
+	long long t = b;
+	t *= t;
+	return t % n;
+}
+
+int expmod(int b, int e, int n)
+{
+	long long t;
+	if (e == 0)
+		return 1;
+
+	t = expmod(b, e/2, n);
+	t = sqrmod(t, n);
+	if (e%2) {
+		t *= b;
+		t %= n;
+	}
+
+	return t;
+}
+
+int mr_test(int test, int n)
+{
+	int s, r;
+	long long t;
+	r = 0;
+	for (s = n-1; s%2==0; s/=2)
+		r++;
+	t = expmod(test, s, n);
+	if (t==1)
+		return 1;
+	while (r--) {
+		if (t==n-1)
+			return 1;
+		t = sqrmod(t, n);
+	}
+	return 0;
+}
+
+/* Miller-Rabin test:
+ * return 1 if considered prime,
+ * otherwise return the proof of non-prime
+ */
+int miller_rabin(const int n)
+{
+	int r;
+	int i;
+
+	if (n==2 || n==3 || n==5 || n==7)
+		return 1;
+
+	if (n%2==0 || n==1)
+		return 0;
+
+	for (i=0; i<100; i++) {
+		do {
+			r = rand() % n;
+		} while (r==0 || r==1 || r==n-1);
+		if (!mr_test(r, n))
+			return r;
+	}
+	return 1;
+}
+
+int make_palindrome(int half, int odd)
+{
+	int s = half;
+	int r = (odd)?half/10:half;
+	while (r) {
+		s = s*10+(r%10);
+		r /= 10;
+	}
+	return s;
+}
+
+int main()
+{
+	FILE *fin, *fout;
+	int a, b;
+	int i,j;
+	int base, base_max;
+	int stopped = 0;
+
+	fin = fopen("pprime.in", "r");
+	fout = fopen("pprime.out", "w");
+
+	fscanf(fin, "%d%d", &a, &b);
+
+	for (base=1; make_palindrome(base, 1)<a; base*=10)
+		;
+	base /= 10;
+
+	while (!stopped) {
+		base_max = base*10-1;
+		for (j=1; j>=0; j--) {
+			for (i=base; i<=base_max; i++) {
+				int t = make_palindrome(i, j);
+				if (t<a)
+					continue;
+				if (t>b) {
+					stopped = 1;
+					break;
+				}
+				if (miller_rabin(t) == 1)
+					fprintf(fout, "%d\n", t);
+			}
+		}
+		base *= 10;
+	}
+
+	fclose(fout);
+	return 0;
+}
diff --git a/1.6/sprime.c b/1.6/sprime.c
new file mode 100644
index 0000000..4611c33
--- /dev/null
+++ b/1.6/sprime.c
@@ -0,0 +1,112 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: sprime
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static int sqrmod(int b, int n)
+{
+	long long t = b;
+	t *= t;
+	return t % n;
+}
+
+int expmod(int b, int e, int n)
+{
+	long long t;
+	if (e == 0)
+		return 1;
+
+	t = expmod(b, e/2, n);
+	t = sqrmod(t, n);
+	if (e%2) {
+		t *= b;
+		t %= n;
+	}
+
+	return t;
+}
+
+int mr_test(int test, int n)
+{
+	int s, r;
+	long long t;
+	r = 0;
+	for (s = n-1; s%2==0; s/=2)
+		r++;
+	t = expmod(test, s, n);
+	if (t==1)
+		return 1;
+	while (r--) {
+		if (t==n-1)
+			return 1;
+		t = sqrmod(t, n);
+	}
+	return 0;
+}
+
+/* Miller-Rabin test:
+ * return 1 if considered prime,
+ * otherwise return the proof of non-prime
+ */
+int miller_rabin(const int n)
+{
+	int r;
+	int i;
+
+	if (n==2 || n==3 || n==5 || n==7)
+		return 1;
+
+	if (n%2==0 || n==1)
+		return 0;
+
+	for (i=0; i<100; i++) {
+		do {
+			r = rand() % n;
+		} while (r==0 || r==1 || r==n-1);
+		if (!mr_test(r, n))
+			return r;
+	}
+	return 1;
+}
+
+static int isprime(int n) { return miller_rabin(n)==1; }
+
+FILE *fin, *fout;
+
+void search_sprime(int N, int s)
+{
+	int i;
+
+	if (N == 0) {
+		fprintf(fout, "%d\n", s);
+		return;
+	}
+
+	if (s == 0) {
+		search_sprime(N-1, 2);
+	}
+	for (i=1; i<=9; i+=2) {
+		if (isprime(s*10+i))
+			search_sprime(N-1, s*10+i);
+	}
+}
+
+
+int main()
+{
+	int N;
+
+	fin = fopen("sprime.in", "r");
+	fout = fopen("sprime.out", "w");
+
+	fscanf(fin, "%d", &N);
+	fclose(fin);
+
+	search_sprime(N, 0);
+	fclose(fout);
+	return 0;
+}
-- 
cgit v1.2.3