62, 504

1 files changed, 73 insertions, 0 deletions

diff --git a/euler504.c b/euler504.c
new file mode 100644
index 0000000..3a7d0da
--- /dev/null
+++ b/euler504.c
@@ -0,0 +1,73 @@
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+int inside[101][101];
+
+int __inside(int a, int b)
+{
+	int count = 0;
+	/* y = -a/b * x + a */
+	for (int i = 1; i < b; i++) {
+		int t = a - (i * a) / b - 1;
+		if (t > 0)
+			count += t;
+	}
+	return count;
+}
+
+void init()
+{
+	for (int i = 1; i <= 100; i++) {
+		for (int j = i; j <= 100; j++) {
+			inside[i][j] = __inside(i, j);
+		}
+	}
+}
+
+int ninside(int a, int b)
+{
+	if (a <= b)
+		return inside[a][b];
+	else
+		return inside[b][a];
+}
+
+int issqr(int x)
+{
+	int sx = sqrt(x);
+	if (sx * sx == x)
+		return 1;
+	else
+		return 0;
+}
+
+int main()
+{
+	int a, b, c, d;
+	int m;
+	int nsqr = 0;
+	init();
+	scanf("%d", &m);
+	for (a = 1; a <= m; a++) {
+		for (b = 1; b <= m; b++) {
+			for (c = a; c <= m; c++) {
+				for (d = b; d <= m; d++) {
+					int count = ninside(a, b) + ninside(a, d)
+						+ ninside(c, b) + ninside(c, d)
+						+ a + b + c + d - 3;
+					if (issqr(count)) {
+						if (a == c && b == d) {
+							nsqr++;
+						} else if (a == c || b == d) {
+							nsqr += 2;
+						} else {
+							nsqr += 4;
+						}
+					}
+				}
+			}
+		}
+	}
+	printf("%d\n", nsqr);
+}