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に近い値が望ましいです。

不可能な場合でも理由をご回答頂ければ幸いです。
宜しくお願いいたします。

回答No.1

masudaya · ベストアンサー

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を探す.
ことで解決可能です.

お礼

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

回答No.2

nakaizu

No1 の方の回答に付け加えます。考え方は同じです

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

お礼

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