diff options
author | Iru Cai <mytbk920423@gmail.com> | 2018-06-11 16:46:43 +0800 |
---|---|---|
committer | Iru Cai <mytbk920423@gmail.com> | 2018-06-11 16:46:43 +0800 |
commit | 9920a766c17402a58fc4457d2fc643cc7905e684 (patch) | |
tree | b966224ecba3cefbd11a74ad1f996dd1e35ee115 /euler346.c | |
parent | 7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5 (diff) | |
download | project_euler-9920a766c17402a58fc4457d2fc643cc7905e684.tar.xz |
112, 345-347
Diffstat (limited to 'euler346.c')
-rw-r--r-- | euler346.c | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/euler346.c b/euler346.c new file mode 100644 index 0000000..dc10d65 --- /dev/null +++ b/euler346.c @@ -0,0 +1,50 @@ +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> + +#define MAXN 1000000000000 +#define NRUMAX 10000000 + +long long ru[NRUMAX]; +int nru = 0; + +int comp(const void *a, const void *b) +{ + long long x = *(long long*)a; + long long y = *(long long*)b; + + if (x < y) + return -1; + else if (x > y) + return 1; + else + return 0; +} + +int main() +{ + long long sum_repunit = 1; /* 1 is a strong repunit */ + for (int base = 2; base < 1000000; base++) { + long long repunit = 1 + base; + long long nb = base; + while (1) { + nb *= base; + repunit += nb; + if (repunit >= MAXN) + break; + assert(nru < NRUMAX); + ru[nru] = repunit; + nru++; + } + } + + qsort(ru, nru, sizeof(long long), comp); + + printf("Find %d strong repunits.\n", nru + 1); + for (int i = 0; i < nru; i++) { + if (i > 0 && ru[i] == ru[i-1]) + continue; + sum_repunit += ru[i]; + } + printf("Their sum is %lld\n", sum_repunit); +} |