• 締切済み

直線で囲まれる領域の格子点問題

y<ax+b、x≧0、y≧0 (a,b 共に有理数で、b>0)の領域内の格子点数を求めたいのですが、どうしても求まりません。教えてください。

みんなの回答

  • MSZ006
  • ベストアンサー率38% (390/1011)
回答No.1

格子点というのは P(x,y):x,yは整数 ということでしょうか?そうだと仮定して、a<0だとする(a>=0だと閉じた領域になりませんので)と、 [-b/a] Σ [na+b] + [-b/a] + 1 n=0 式がわかりにくいですが、シグマの引数n で、nを0から[-b/a] まで変化させる、シグマが係っているのは[na+b]だけです。また、[ ]は関数?で、中身の数未満の最大の整数です。 こんなので回答になっていますか?

_hitoshi_
質問者

お礼

質問の内容に不備があったことをお詫びします。 a<0 の条件が必要です。 この質問の目的は有理数で示される数列の整数部分の和をもとめることでした。 それが結局、格子点問題に帰着すると判断して、格子点問題として質問した次第です。従って、頂いた回答は私にとっては問題が元に戻ってしまうことになります。 尚、この数列の和の演算は、コンピュータで計算したいと思っており、1項ずつ加算していくのでは時間がかかりすぎてしまうため、一括で計算したいと考えていました。しかし、仮に一括で計算する計算式が求まったとしても、少しでも複雑な計算式になると、丸め誤差による誤差は免れないため、高速で計算できるアルゴリズムを考えたほうが妥当と考え直しました。 質問の回答をありがとうございました。

関連するQ&A

専門家に質問してみよう