• ベストアンサー

a mod b = x、c mod d = x

a mod b = x c mod d = x (a,b,c,dは正の整数) という式が与えられ aとbとdの数値が決定している場合に cの値を求める事は可能でしょうか? ただしこのとき 計算途中にxの値を使わずcの値を求めたいのです。(瞬間的にでもメモリ(レジスタ含む)にその数値を書きたくない為) 例えば 49999 % 800 = 399 c mod 1560 = 399 この場合cは50319や51879等あると思いますが49999に近い値が望ましいです。 不可能な場合でも理由をご回答頂ければ幸いです。 宜しくお願いいたします。

質問者が選んだベストアンサー

  • ベストアンサー
  • masudaya
  • ベストアンサー率47% (250/524)
回答No.1

a mod b = x c mod d = x ということは, a=bk+x (1) c=dh+x (2) ということです.(k,h∈N) 今k=int(a/b)を保存できれば(1)-(2)は a-c=bk-dh (3) となり,hを変化させながら|a-c|が最小になる,hを探す. ことで解決可能です. xを使っていいなら a-c=a-dh-x (4) としてhを変化させながら|a-c|が最小になる,hを探す. ことで解決可能です.

sha-girl
質問者

お礼

お答え頂き有り難うございます。 計算式、非常に参考になりました。

その他の回答 (1)

  • nakaizu
  • ベストアンサー率48% (203/415)
回答No.2

No1 の方の回答に付け加えます。考え方は同じです k=int(a/b) h=int(a/d) とします。int は切捨てです。 c=a+dh-bk とすればcを求められます。 ただし、誤差の限界はmax(b,d)ですのでbがdにくらべて大きいときはa にもっとも近いとは言えない場合があります。 その場合はdh-bkが小さくなるようにhを変化させてください。

sha-girl
質問者

お礼

お二方の詳しい回答のおかげで、問題を解決する事が出来ました。 有り難うございます。

関連するQ&A

専門家に質問してみよう