Source code for submission s449

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

Diff to submission s448

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