Source code for submission s762

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

Diff to submission s750

fl.cpp

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