Go to diff to previous submission
#include <cstdio> #include <vector> #include <utility> #include <cstring> 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); } int findlcm(int a, int b) { return a * b / gcd(a, b); } int main() { int k, bl; unsigned int results[10010]; memset(results, 0, sizeof(results)); while (scanf("%d/%d", &bl, &k) == 2) { unsigned int result; if (results[k] > 0) { result = results[k]; } else { 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)); } result = egypt.size(); results[k] = result; } printf("%u\n", result); } }
--- c5.s448.cteam063.fl.cpp.0.fl.cpp +++ c5.s449.cteam063.fl.cpp.0.fl.cpp @@ -2,4 +2,5 @@ #include <vector> #include <utility> +#include <cstring> int gcd(int a, int b) @@ -21,16 +22,30 @@ { int k, bl; + + unsigned int results[10010]; + memset(results, 0, sizeof(results)); + while (scanf("%d/%d", &bl, &k) == 2) { - std::vector< std::pair<int, int> > egypt; - for (int i = k + 1; i <= 2 * k; i++) + unsigned int result; + 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)); + result = results[k]; + } + else + { + 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)); + } + result = egypt.size(); + results[k] = result; } - printf("%u\n", egypt.size()); + printf("%u\n", result); } }