leetcode

commit 6755614b862ad4b6c914194d061fdef9e6646d6c
parent 88ae2cc953fbe1dfa4a77b361605103efa8597b6
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon,  8 Dec 2025 16:54:18 +0100

1925. count square sum triples

Diffstat:
A
count_square_sum_triple.c
 | 
37
+++++++++++++++++++++++++++++++++++++
A
count_square_sum_triple.py
 | 
32
++++++++++++++++++++++++++++++++

2 files changed, 69 insertions(+), 0 deletions(-)
diff --git a/count_square_sum_triple.c b/count_square_sum_triple.c
@@ -0,0 +1,37 @@
+// 1925. Count Square Sum Triples
+#include "leetcode.h"
+
+/*
+ * a square triple '(a, b, c)' is a triple where 'a', 'b', and 'c' are integers
+ * and 'a^2 + b^2 = c^2'. given an integer 'n', return the number of square
+ * triples such that '1 <= a, b, c <= n'.
+ */
+
+int gcd(int a, int b) {
+  while (b != 0) {
+    int tmp = b;
+    b = a % b;
+    a = tmp;
+  }
+  return a;
+}
+
+int countTriples(int n) {
+  int ans = 0;
+  for (int u = 2; u <= sqrt(n); u++) {
+    for (int v = 1; v < u; v++) {
+      if (~(u - v) & 1 || gcd(u, v) != 1)
+        continue;
+      int c = u * u + v * v;
+      if (c > n)
+        continue;
+      ans += (n / c) << 1;
+    }
+  }
+  return ans;
+}
+
+int main() {
+  printf("%d\n", countTriples(5));  // expect: 2
+  printf("%d\n", countTriples(10)); // expect: 4
+}
diff --git a/count_square_sum_triple.py b/count_square_sum_triple.py
@@ -0,0 +1,32 @@
+# 1925. Count Square Sum Triples
+import math
+
+"""
+a square triple '(a, b, c)' is a triple where 'a', 'b', and 'c' are integers
+and 'a^2 + b^2 = c^2'. given an integer 'n', return the number of square
+triples such that '1 <= a, b, c <= n'.
+"""
+
+
+class Solution(object):
+    def countTriples(self, n):
+        """
+        :type n: int
+        :rtype: int
+        """
+        ans = 0
+        for u in range(2, int(math.sqrt(n)) + 1):
+            for v in range(1, u):
+                if (u - v) & 1 == 0 or math.gcd(u, v) != 1:
+                    continue
+                c = u * u + v * v
+                if c > n:
+                    continue
+                ans += 2 * (n // c)
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countTriples(n=5))
+    print(obj.countTriples(n=10))