Source code for submission s750

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. 	unsigned int results[10010];
  38. 	memset(results, 0, sizeof(results));
  39.  
  40. 	gcdmem = new int[20020 * 20020];
  41. 	memset(gcdmem, 0, sizeof(int) * 20020 * 20020);
  42.  
  43. 	while (scanf("%d/%d", &bl, &k) == 2)
  44. 	//~ for (int k = 200; k < 500; k++)
  45. 	{
  46. 		if (results[k] == 0)
  47. 		{
  48. 			std::vector< std::pair<int, int> > egypt;
  49. 			for (int i = k + 1; i <= 2 * k; i++)
  50. 			{
  51. 				int lcm = findlcm(i, k);
  52. 				int nom = (lcm / k) - (lcm / i);
  53. 				if (lcm % nom == 0)
  54. 					egypt.push_back(std::make_pair(lcm / nom, 1));
  55. 			}
  56. 			results[k] = egypt.size();
  57. 		}
  58.  
  59. 		printf("%u\n", results[k]);
  60. 		//~ printf("k=%d: %u\n", k, results[k]);
  61. 	}
  62.  
  63. 	return 0;
  64. }
  65.  

Diff to submission s502

fl.cpp

--- c5.s502.cteam063.fl.cpp.0.fl.cpp
+++ c5.s750.cteam063.fl.cpp.0.fl.cpp
@@ -4,28 +4,29 @@
 #include <cstring>
 
-int **gcdmem;
-int **lcmmem;
+int *gcdmem;
 
 int gcd(int a, int b)
 {
-        if (gcdmem[a][b] == 0)
+        if (gcdmem[a*20020+b] == 0)
         {
                 if (a == b)
-                        gcdmem[a][b] = a;
+                        gcdmem[a*20020+b] = a;
                 else if (a > b)
-                        gcdmem[a][b] = gcd(a -b, b);
+                        gcdmem[a*20020+b] = gcd(a - b, b);
                 else
-                        gcdmem[a][b] = gcd(a, b - a);
+                        gcdmem[a*20020+b] = gcd(a, b - a);
         }
         
-        return gcdmem[a][b];
+        return gcdmem[a*20020+b];
 }
 
 int findlcm(int a, int b)
 {
-        if (lcmmem[a][b] == 0)
-                lcmmem[a][b] = a * b / gcd(a, b);
+        return a * b / gcd(a, b);
         
-        return lcmmem[a][b];
+        //~ if (lcmmem[a*20020+b] == 0)
+                //~ lcmmem[a*20020+b] = a * b / gcd(a, b);
+        
+        //~ return lcmmem[a*20020+b];
 }
 
@@ -37,19 +38,9 @@
         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);
-        }
+        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)
@@ -67,4 +58,5 @@
                 
                 printf("%u\n", results[k]);
+                //~ printf("k=%d: %u\n", k, results[k]);
         }