summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIru Cai <mytbk920423@gmail.com>2018-04-16 21:15:33 +0800
committerIru Cai <mytbk920423@gmail.com>2018-04-16 21:15:33 +0800
commit235aef5fae393c738e78a5b188051557b6ebd97c (patch)
tree732806180be4a6cc75c0cea4511d022eda1d7856
parentad4e2420e822b8a115aac6124307b89447578782 (diff)
downloadusaco-235aef5fae393c738e78a5b188051557b6ebd97c.tar.xz
1.6
-rw-r--r--1.6/numtri.c39
-rw-r--r--1.6/pprime.c124
-rw-r--r--1.6/sprime.c112
3 files changed, 275 insertions, 0 deletions
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;
+}