ピタゴラス数の列挙

前にもやったが、このとき言及した別方針でやりましょう。

より一般に、2次曲線C上の有理点を列挙します。
・どうにかしてC上の有理点Pを1つ見つける
・Pを通る傾き有理数の直線Lと、LとCの交点であってPでない方が一対一対応

証明：
・有理点を結ぶ直線の傾きは有理数である
→自明
・2次曲線上の有理点を通り傾きが有理数の直線とその2次曲線のもう一つの交点は有理点
→解と係数の関係から自明
証明終わり

2次斉次3変数方程式の解を列挙することができるようになりました
・X^2+Y^2=Z^2 → x^2+y^2=1と(1,0)を使う
・X^2+XY+Y^2=Z^2 → x^2+xy+y^2=1と(1,0)を使う
・X^2-2Y^2=Z^2 → x^2-2y^2=1と(1,0)を使う

おわり

互いに素な整数の組の列挙

Euler296のThreadから

問題：互いに素な正整数の組x,yであって、x+y<=n (など、x,yについて単調な何らかの条件)を満たす組を順序不問で全て列挙せよ

この問題は愚直にやるとgcdのlogがついてO(ans*log)になる。
Stern-Brocot treeを使うとgcdが不要になりO(ans)になるが、空間O(n)などになる
Stern-Brocot treeを使うアプローチで空間O(1)にすると時間にlogがつくと思う

実は時間O(ans)空間O(1)でできます

続きを読む »