diff options
| -rw-r--r-- | 1.6/numtri.c | 39 | ||||
| -rw-r--r-- | 1.6/pprime.c | 124 | ||||
| -rw-r--r-- | 1.6/sprime.c | 112 |
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; +} |