Go to diff to previous submission
#include <cstdio> #include <vector> #include <utility> #include <cstring> int *gcdmem; int gcd(int a, int b) { if (a < b) return gcd(b, a); if (a % 2 == 0) { if (gcdmem[(a/2)*10020+b] == 0) { if (a == b) gcdmem[(a/2)*10020+b] = a; else if (a > b) gcdmem[(a/2)*10020+b] = gcd(a - b, b); else gcdmem[(a/2)*10020+b] = gcd(a, b - a); } return gcdmem[(a/2)*10020+b]; } else { if (a == b) return a; else if (a > b) return gcd(a - b, b); else return gcd(a, b - a); } } int findlcm(int a, int b) { return a * b / gcd(a, b); //~ if (lcmmem[a*20020+b] == 0) //~ lcmmem[a*20020+b] = a * b / gcd(a, b); //~ return lcmmem[a*20020+b]; } int main() { int k, bl; try { unsigned int results[10010]; memset(results, 0, sizeof(results)); gcdmem = new int[10020 * 10020]; memset(gcdmem, 0, sizeof(int) * 10020 * 10020); while (scanf("%d/%d", &bl, &k) == 2) //~ for (int k = 10000; k > 1; k--) { if (results[k] == 0) { for (int i = k + 1; i <= 2 * k; i++) { int lcm = findlcm(i, k); int nom = (lcm / k) - (lcm / i); if (lcm % nom == 0) results[k]++; } } printf("%u\n", results[k]); //~ printf("k=%d: %u\n", k, results[k]); } } catch (std::bad_alloc) { return 0; } return 0; }
--- c5.s762.cteam063.fl.cpp.0.fl.cpp +++ c5.s781.cteam063.fl.cpp.0.fl.cpp @@ -8,15 +8,29 @@ int gcd(int a, int b) { - if (gcdmem[a*20020+b] == 0) + if (a < b) + return gcd(b, a); + + if (a % 2 == 0) + { + if (gcdmem[(a/2)*10020+b] == 0) + { + if (a == b) + gcdmem[(a/2)*10020+b] = a; + else if (a > b) + gcdmem[(a/2)*10020+b] = gcd(a - b, b); + else + gcdmem[(a/2)*10020+b] = gcd(a, b - a); + } + return gcdmem[(a/2)*10020+b]; + } + else { if (a == b) - gcdmem[a*20020+b] = a; + return a; else if (a > b) - gcdmem[a*20020+b] = gcd(a - b, b); + return gcd(a - b, b); else - gcdmem[a*20020+b] = gcd(a, b - a); + return gcd(a, b - a); } - - return gcdmem[a*20020+b]; } @@ -40,6 +54,6 @@ memset(results, 0, sizeof(results)); - gcdmem = new int[20020 * 20020]; - memset(gcdmem, 0, sizeof(int) * 20020 * 20020); + gcdmem = new int[10020 * 10020]; + memset(gcdmem, 0, sizeof(int) * 10020 * 10020); while (scanf("%d/%d", &bl, &k) == 2)