CodeIQ「『スクエア・カルテット』問題」の出題期間が終了したということで、自分が提出したコードを公表してみたいと思います。最初はPythonで書いており、実際に提出までしたのですが――なぜか途中で気が変わりSchemeへと変更。おそらくPythonについてはだれかほかの方がコードを公開してくれると思うので、自分はユーザーの少ないSchemeに絞りたいと思います。
2016/11/17追記:
公開されたコードについて出題者の@riverplusさんがまとめてくださっていたようです。わたしはこれから勉強します(´・ω・`)
http://togetter.com/li/922419
; n(= b*b-a*a)があたえられたとき、ありうるpとq(p > q)の組み合わせを作り、リストに格納する
; (make-pq-list 91) => '((13 . 7) (91 . 1)) [約数]
(define (make-pq-list n)
(let loop ((q 1) (pq-list '()))
(if (>= q (sqrt n))
pq-list
(loop (+ q 1)
(if (zero? (modulo n q))
(cons `(,(quotient n q) . ,q) pq-list)
pq-list)))))
; 問題文のF(a, b)
; (F 3 10) => 104
(define (F a b)
(let loop ((pq-list (make-pq-list (- (* b b) (* a a)))) (sum 0))
(if (null? pq-list)
sum
(let ((p (car (car pq-list))) (q (cdr (car pq-list))))
(loop (cdr pq-list)
(if (even? (+ p q)) ; p + qが偶数のとき、p - qも偶数
(+ sum p) ; p = x + y
sum))))))
; メイン関数。入力を処理して関数Fに渡し、その結果を出力する
(define (MAIN)
(let* ((a (read)) (b (read)))
(write (F a b))))
(MAIN)
; == 方針 ==
; x ** 2 + a ** 2 = y ** 2 + b ** 2
; <=> x ** 2 - y ** 2 = b ** 2 - a ** 2
; <=> (x + y)(x - y) = b ** 2 - a ** 2
; x + y = p, x - y = q, b ** 2 - a ** 2 = n (p > q, nは0以上の整数)とすると
; p = x + y <=> x = (p + q) / 2
; q = x - y <=> y = (p - q) / 2
; n = p * q
; p, qがとりうる値はnの約数であることを利用して求める
; p, qがわかればx, yおよびx + yの値も決定する
; ただしx, yは自然数、つまりp + q, p - qはともに偶数である必要がある
アルゴリズムについては下部の「方針」に書いた通り――というかあれ以上にどう書いていいのか、わたしにはわかりません(´・ω・`)。数学的な説明はわたしより何倍も偉い人が書いてくれるはずなので、わたしも今から期待しています。
ちなみにCodeIQで採用されているSchemeの処理系はGuile1.8.5です。この手のサイトでSchemeが利用できるのは珍しいのですが、処理系はやや古いので、CodeIQに関心がある全国20億人のSchemeプログラマのみなさんはお気を付けを。