Go to diff to previous submission
#include <cstdio> #include <vector> #include <utility> #include <cstring> int **gcdmem; int **lcmmem; int gcd(int a, int b) { if (gcdmem[a][b] == 0) { if (a == b) gcdmem[a][b] = a; else if (a > b) gcdmem[a][b] = gcd(a -b, b); else gcdmem[a][b] = gcd(a, b - a); } return gcdmem[a][b]; } int findlcm(int a, int b) { if (lcmmem[a][b] == 0) lcmmem[a][b] = a * b / gcd(a, b); return lcmmem[a][b]; } int main() { int k, bl; unsigned int results[10010]; memset(results, 0, sizeof(results)); gcdmem = new int*[10010]; for (unsigned int i = 0; i < 10010; i++) { gcdmem[i] = new int[10010]; memset(gcdmem[i], 0, sizeof(int)*10010); } lcmmem = new int*[10010]; for (unsigned int i = 0; i < 10010; i++) { lcmmem[i] = new int[10010]; memset(lcmmem[i], 0, sizeof(int)*10010); } while (scanf("%d/%d", &bl, &k) == 2) { if (results[k] == 0) { std::vector< std::pair<int, int> > egypt; for (int i = k + 1; i <= 2 * k; i++) { int lcm = findlcm(i, k); int nom = (lcm / k) - (lcm / i); if (lcm % nom == 0) egypt.push_back(std::make_pair(lcm / nom, 1)); } results[k] = egypt.size(); } printf("%u\n", results[k]); } return 0; }
--- c5.s459.cteam063.fl.cpp.0.fl.cpp +++ c5.s502.cteam063.fl.cpp.0.fl.cpp @@ -4,17 +4,28 @@ #include <cstring> +int **gcdmem; +int **lcmmem; + int gcd(int a, int b) { - if (a == b) - return a; - else if (a > b) - return gcd(a -b, b); - else - return gcd(a, b - a); + if (gcdmem[a][b] == 0) + { + if (a == b) + gcdmem[a][b] = a; + else if (a > b) + gcdmem[a][b] = gcd(a -b, b); + else + gcdmem[a][b] = gcd(a, b - a); + } + + return gcdmem[a][b]; } int findlcm(int a, int b) { - return a * b / gcd(a, b); + if (lcmmem[a][b] == 0) + lcmmem[a][b] = a * b / gcd(a, b); + + return lcmmem[a][b]; } @@ -26,12 +37,21 @@ memset(results, 0, sizeof(results)); + gcdmem = new int*[10010]; + for (unsigned int i = 0; i < 10010; i++) + { + gcdmem[i] = new int[10010]; + memset(gcdmem[i], 0, sizeof(int)*10010); + } + + lcmmem = new int*[10010]; + for (unsigned int i = 0; i < 10010; i++) + { + lcmmem[i] = new int[10010]; + memset(lcmmem[i], 0, sizeof(int)*10010); + } + while (scanf("%d/%d", &bl, &k) == 2) { - unsigned int result; - if (results[k] > 0) - { - result = results[k]; - } - else + if (results[k] == 0) { std::vector< std::pair<int, int> > egypt; @@ -43,9 +63,8 @@ egypt.push_back(std::make_pair(lcm / nom, 1)); } - result = egypt.size(); - results[k] = result; + results[k] = egypt.size(); } - printf("%u\n", result); + printf("%u\n", results[k]); }