192 : 最適近似値

$x$を実数とする. 分母の範囲が$d$での$x$の最適近似値とは次の条件を満たす既約の有理数$r/s$である: $s ≤ d$で, $r/s$より$x$に近い全ての既約の有理数は分母が$d$より大きい, つまり:

$|p/q-x| < |r/s-x| ⇒ q > d$

例えば分母の範囲が$20$での$\sqrt{13}$の最適近似値は$18/5$であり, 分母の範囲が$30$での$\sqrt{13}$の最適近似値は$101/28$である.

$1 < n ≤ 100000$で平方数でない$n$に対して, 分母の範囲が$10^{12}$での$\sqrt{n}$の最適近似値の全ての分母の合計を求めよ.