From 1eefd58ca4fdb5d2f51f657bfd70c9a89a4707db Mon Sep 17 00:00:00 2001 From: Iru Cai Date: Thu, 24 May 2018 21:39:58 +0800 Subject: initial commit --- euler44.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) create mode 100644 euler44.c (limited to 'euler44.c') diff --git a/euler44.c b/euler44.c new file mode 100644 index 0000000..db032aa --- /dev/null +++ b/euler44.c @@ -0,0 +1,58 @@ +#include +#include + +long long Pn(int n) +{ + return (long long)n*(long long)(3*n-1)/2; +} + +#define MAXSIZE (1<<22) +long long P[MAXSIZE]; + +int comp(const void *a, const void *b) +{ + long long aa = *(long long*)a; + long long bb = *(long long*)b; + if (aa < bb) + return -1; + if (aa > bb) + return 1; + return 0; +} + +int main() +{ + int i, j; + int range = (1<<15); + for (i = 1; i < range; i++) + P[i] = Pn(i); + + /* i < 257 is impossible when searching with range=(1<<15) */ + /* i < 725 is impossible with range=(1<<18) */ + /* i < 1449 is impossible with range=(1<<20) */ + for (i = 1; i < range; i++) { + long long diff = P[i]; + for (j = 1; j < range - 1; j++) { + long long Pj = P[j]; + long long Pk = Pj + diff; + long long Pjk = Pj + Pk; + if (Pk < P[j+1]) + break; + while (Pjk > P[range-1]) { + int newrange = range * 2; + int r; + for (r = range; r < newrange; r++) + P[r] = Pn(r); + range = newrange; + } + if (!bsearch(&Pk, P+1, range-1, sizeof(long long), comp)) + continue; + if (!bsearch(&Pjk, P+1, range-1, sizeof(long long), comp)) + continue; + printf("i = %d, D = %lld, j = %d, P[j] = %lld\n", i, diff, j, Pj); + /* i = 1912, D = 5482660, j = 1020, P[j] = 1560090 */ + return 0; + } + printf("i = %d\n", i); + } +} -- cgit v1.2.3