Source code for submission s781

Go to diff to previous submission

#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
 
int *gcdmem;
 
int gcd(int a, int b)
{
	if (a < b)
		return gcd(b, a);
 
	if (a % 2 == 0)
	{
		if (gcdmem[(a/2)*10020+b] == 0)
		{
			if (a == b)
				gcdmem[(a/2)*10020+b] = a;
			else if (a > b)
				gcdmem[(a/2)*10020+b] = gcd(a - b, b);
			else
				gcdmem[(a/2)*10020+b] = gcd(a, b - a);
		}
		return gcdmem[(a/2)*10020+b];
	}
	else
	{
		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);
 
	//~ if (lcmmem[a*20020+b] == 0)
		//~ lcmmem[a*20020+b] = a * b / gcd(a, b);
 
	//~ return lcmmem[a*20020+b];
}
 
int main()
{
	int k, bl;
 
	try {
 
		unsigned int results[10010];
		memset(results, 0, sizeof(results));
 
		gcdmem = new int[10020 * 10020];
		memset(gcdmem, 0, sizeof(int) * 10020 * 10020);
 
		while (scanf("%d/%d", &bl, &k) == 2)
		//~ for (int k = 10000; k > 1; k--)
		{
			if (results[k] == 0)
			{
				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]++;
				}
			}
 
			printf("%u\n", results[k]);
			//~ printf("k=%d: %u\n", k, results[k]);
		}
	}
	catch (std::bad_alloc)
	{
		return 0;
	}
 
	return 0;
}
 

Diff to submission s762

--- c5.s762.cteam063.fl.cpp.0.fl.cpp
+++ c5.s781.cteam063.fl.cpp.0.fl.cpp
@@ -8,15 +8,29 @@
 int gcd(int a, int b)
 {
-        if (gcdmem[a*20020+b] == 0)
+        if (a < b)
+                return gcd(b, a);
+        
+        if (a % 2 == 0)
+        {
+                if (gcdmem[(a/2)*10020+b] == 0)
+                {
+                        if (a == b)
+                                gcdmem[(a/2)*10020+b] = a;
+                        else if (a > b)
+                                gcdmem[(a/2)*10020+b] = gcd(a - b, b);
+                        else
+                                gcdmem[(a/2)*10020+b] = gcd(a, b - a);
+                }
+                return gcdmem[(a/2)*10020+b];
+        }
+        else
         {
                 if (a == b)
-                        gcdmem[a*20020+b] = a;
+                        return a;
                 else if (a > b)
-                        gcdmem[a*20020+b] = gcd(a - b, b);
+                        return gcd(a - b, b);
                 else
-                        gcdmem[a*20020+b] = gcd(a, b - a);
+                        return gcd(a, b - a);
         }
-        
-        return gcdmem[a*20020+b];
 }
 
@@ -40,6 +54,6 @@
                 memset(results, 0, sizeof(results));
                 
-                gcdmem = new int[20020 * 20020];
-                memset(gcdmem, 0, sizeof(int) * 20020 * 20020);
+                gcdmem = new int[10020 * 10020];
+                memset(gcdmem, 0, sizeof(int) * 10020 * 10020);
                 
                 while (scanf("%d/%d", &bl, &k) == 2)