※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。



Problem 75 「1通りの整数直角三角形」 †

ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである. 他にも沢山の例が挙げられる.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Lを鉄線の長さとする. 直角三角形を作るときに1通りの折り曲げ方しか存在しないような L ≤ 1,500,000 の総数を答えよ.

注: この問題は最近変更されました. あなたが正しいパラメータを使っているか確認してください.


解法
原始ピタゴラス数とそれを相似拡大したもの全てを求め、そのリストをソートして一個しかないものを抽出します。
Prolog言語なので集合の概念から攻めますがC++ならもうちょっと賢い方法がありそうです。


gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).

count_one([],_,1,1):-!.
count_one([],_,_,0):-!.
count_one([L|Ls],L,Count,Result):-
	!,
	Count1 is Count+1,
	count_one(Ls,L,Count1,Result).
count_one([L|Ls],_,1,Result):-
	!,
	count_one(Ls,L,1,Re),
	Result is Re+1.
count_one([L|Ls],_,_,Result):-
	count_one(Ls,L,1,Result).

searchBai(L,_,_):-L>1500000,!,fail.
searchBai(L,_,L).
searchBai(L,Add,Result):-
	L1 is L+Add,
	searchBai(L1,Add,Result).

searchN(M,L1):-
	between(1,M,N),
	N<M,
	((M-N) mod 2)=:=1,
 	gcd(N,M,G),
	G=:=1,
	L is 2*M*(M+N),
	(L>1500000 -> !,fail;true),
	searchBai(L,L,L1)
 	.

searchM(L1):-
	between(2,4000,M),
 	searchN(M,L1).

main75:-
	findall(L1,searchM(L1),Lens),
	msort(Lens,[L|Lens1]),
	count_one(Lens1,L,1,Ans),
	write(Ans).