Source code for submission s502

Go to diff to previous submission

fl.cpp

  1. #include <cstdio>
  2. #include <vector>
  3. #include <utility>
  4. #include <cstring>
  5.  
  6. int **gcdmem;
  7. int **lcmmem;
  8.  
  9. int gcd(int a, int b)
  10. {
  11. if (gcdmem[a][b] == 0)
  12. {
  13. if (a == b)
  14. gcdmem[a][b] = a;
  15. else if (a > b)
  16. gcdmem[a][b] = gcd(a -b, b);
  17. else
  18. gcdmem[a][b] = gcd(a, b - a);
  19. }
  20.  
  21. return gcdmem[a][b];
  22. }
  23.  
  24. int findlcm(int a, int b)
  25. {
  26. if (lcmmem[a][b] == 0)
  27. lcmmem[a][b] = a * b / gcd(a, b);
  28.  
  29. return lcmmem[a][b];
  30. }
  31.  
  32. int main()
  33. {
  34. int k, bl;
  35.  
  36. unsigned int results[10010];
  37. memset(results, 0, sizeof(results));
  38.  
  39. gcdmem = new int*[10010];
  40. for (unsigned int i = 0; i < 10010; i++)
  41. {
  42. gcdmem[i] = new int[10010];
  43. memset(gcdmem[i], 0, sizeof(int)*10010);
  44. }
  45.  
  46. lcmmem = new int*[10010];
  47. for (unsigned int i = 0; i < 10010; i++)
  48. {
  49. lcmmem[i] = new int[10010];
  50. memset(lcmmem[i], 0, sizeof(int)*10010);
  51. }
  52.  
  53. while (scanf("%d/%d", &bl, &k) == 2)
  54. {
  55. if (results[k] == 0)
  56. {
  57. std::vector< std::pair<int, int> > egypt;
  58. for (int i = k + 1; i <= 2 * k; i++)
  59. {
  60. int lcm = findlcm(i, k);
  61. int nom = (lcm / k) - (lcm / i);
  62. if (lcm % nom == 0)
  63. egypt.push_back(std::make_pair(lcm / nom, 1));
  64. }
  65. results[k] = egypt.size();
  66. }
  67.  
  68. printf("%u\n", results[k]);
  69. }
  70.  
  71. return 0;
  72. }
  73.  

Diff to submission s459

fl.cpp

--- 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]);
         }