[答1930] 互いに素な約数
次のＮの２つの正の約数 m，n が 互いに素で m＞n を満たす (m，n)の組の個数は？
(1) N＝100000000 のとき (2) N＝113400000 のとき
[解答]
(1) N＝100000000＝28･58 です。
P＝2a･5b (a，b は整数で、－8≦a≦8 ，－8≦b≦8)
の、17･17＝289 通りのPのうち、a＝b＝0 のとき P＝1 です。
また、P＞1 の場合と P＜1 の場合は同数で、逆数どうし 1対1に対応します。
分子･分母の大きい方を m ，小さい方を n とすればよいので、
(289－1)/2＝144 組あります。
(2) N＝113400000＝26･55･34･7 です。
P＝2a･5b･3c･7d
(a，b，c，d は整数で、－6≦a≦6 ，－5≦b≦5 ，－4≦c≦4 ，－1≦d≦1)
の、13･11･9･3＝3861 通りのPのうち、a＝b＝c＝d＝0 のとき P＝1 です。
また、P＞1 の場合と P＜1 の場合は同数で、逆数どうし 1対1に対応します。
分子･分母の大きい方を m ，小さい方を n とすればよいので、
(3861－1)/2＝1930 組あります。
[参考] たけちゃんさんのコメントより
N＝26･55･34･7 の異なるいくつか(ｋ個)の正の約数が，
「どの2数も最大公約数が１」をみたすような約数の組
(ただし，順番違いは同一視)を求める問題も考えられます．
この組数を ak とし，特に，約数1を含まない組の数を bk とします．
k＝1 なら，約数の個数がそのまま結論で，
a1＝7･5･6･2＝420 ，b1＝a1－1＝419. です．
k＝2 なら，本問そのものであり，
a2＝(13･9･11･3－1)/2＝1930 ，b2＝a2－b1＝1511 となります．
k＝3 のときは，いったん3個の約数を x，y，z と区別することで，
例えば素因数2については，x，y，z のどれかが 1～6 個含むか，どれも含まない
となって 19通りがあり得ることになり，他の素因数についても同様だから，
「同じもの(１しかあり得ない)を含んでもよい，順番違いも区別」であれば
19･13･16･4通り です．
１を３つ含む１通り，１を２つ含む b1･3C2 通りを除いて，順番の区別をなくして，
a3＝(19･13･16･4－1－b1･3C2)/3!＝2425 ，b3＝a3－b2＝914 です．
k＝4 のときも同様に考えて，
a4＝(25･17･21･5－1－b1･4C3－b2･4C2･2!)/4!＝1034，
b4＝a4－b3＝120 となります．
ただし，b4 は，
4つの約数が2の累乗，3の累乗，5の累乗，7の累乗に限る
ことから，容易に6･4･5･1＝120 と求まり，
a4＝b4＋b3 として求める方が楽ではあります．
さらに，b5＝0 ，a5＝b4＝120 であることは明らかでしょう．
.
