Go to diff to previous submission
#include <cstdio> #include <vector> #include <utility> #include <cstring> int *gcdmem; int gcd(int a, int b) { if (gcdmem[a*20020+b] == 0) { if (a == b) gcdmem[a*20020+b] = a; else if (a > b) gcdmem[a*20020+b] = gcd(a - b, b); else gcdmem[a*20020+b] = gcd(a, b - a); } return gcdmem[a*20020+b]; } 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[20020 * 20020]; memset(gcdmem, 0, sizeof(int) * 20020 * 20020); 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.s750.cteam063.fl.cpp.0.fl.cpp +++ c5.s762.cteam063.fl.cpp.0.fl.cpp @@ -35,28 +35,33 @@ int k, bl; - unsigned int results[10010]; - memset(results, 0, sizeof(results)); - - gcdmem = new int[20020 * 20020]; - memset(gcdmem, 0, sizeof(int) * 20020 * 20020); - - while (scanf("%d/%d", &bl, &k) == 2) - //~ for (int k = 200; k < 500; k++) - { - if (results[k] == 0) + try { + + unsigned int results[10010]; + memset(results, 0, sizeof(results)); + + gcdmem = new int[20020 * 20020]; + memset(gcdmem, 0, sizeof(int) * 20020 * 20020); + + while (scanf("%d/%d", &bl, &k) == 2) + //~ for (int k = 10000; k > 1; k--) { - std::vector< std::pair<int, int> > egypt; - for (int i = k + 1; i <= 2 * k; i++) + if (results[k] == 0) { - int lcm = findlcm(i, k); - int nom = (lcm / k) - (lcm / i); - if (lcm % nom == 0) - egypt.push_back(std::make_pair(lcm / nom, 1)); + 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]++; + } } - results[k] = egypt.size(); + + printf("%u\n", results[k]); + //~ printf("k=%d: %u\n", k, results[k]); } - - printf("%u\n", results[k]); - //~ printf("k=%d: %u\n", k, results[k]); + } + catch (std::bad_alloc) + { + return 0; }