ａ×ｂ＝ｃ でキレイなｃになるａとｂの求め方

質問

宜しくお願いします。

例えば、
932,640×18,750＝17,487,000,000
453,120×96,875＝43,896,000,000

のように、ａ×ｂ＝ｃ でｃの下の位が、希望の桁だけゼロになるような、
ａとｂを求める方法をさがしております。
最も単純なのは、乱数を使ってひたすら掛けてみる方法だと思いますが、
もっとかしこくて効率的なアルゴリズムはないでしょうか？

回答No.1

elmclose · ベストアンサー

ｃの下の位がｎ個連続してゼロになるということは、ｃを素因数分解したときに、２をｎ個、そして５をｎ個は含むということです。

したがって、それらを含む、ａおよびｂを求めればよいということになります。

例えば、ゼロを１０個含ませるようにするためには、２を１０個、５を１０個含ませればよいわけで、一例としては、
ａ＝２＾１０＊（任意の整数）
ｂ＝５＾１０＊（任意の整数）
とすれば、できます。　　（＾はべき乗を表わす）

疑問があれば、さらに質問してください。

補足

早速のレスですばらしい解答をありがとうございます。
実際に色々とやってみましたが、すごいです（感動）。
で、実はもう一つありまして、できればそちらも．．．

例えば、ゼロが５桁の場合、
132,896×46,875＝6,229,500,000 → ＯＫ
144,384×34,375＝4,963,200,000 → ＮＧ

のように、ここで求めたａとｂの数字が、
ａｂ各位の数字の０～９が同じにならないようにしたいのです。
（ａはａの中で、ｂはｂの中でです）
今回、ご教授して頂いた方法だけでもすばらしく、
試行錯誤でも何回かやれば出そうですが．．．
宜しくお願いします。

回答No.6

arukamun

希望の0の桁数をn>1
a*b=c
として、
aやbのどちらかは１の位は0,2,4,5,6,8の何れかに限定されますね。
cには必ず末尾に0が付く事から、aとbをどちらかを2系、もう片方を5系と分ける事が出来ます。
仮にaを2系とすると、0,2,4,6,8
bを5系とすると、0,5
と下一桁が変化する様にfor文の第３パラメータを設定すれば良いでしょうね。

また、n個の2と5をaかbのどちらかに掛けなくてはいけないので、
aには既に2を一回掛けている事、bには既に5を一回掛けている事を踏まえて、n-1個の2とn-1個の5をいろいろなケースを考えて振り分けなくてはなりませんね。
ここで、2*2*5*5=100になる事から、aやbは100の倍数になっては下二桁が00になり題意に反するので、この様にならないようにn-1個の2とn-1個の5を振り分ければ良いわけです。

こういったいろいろな事柄を枝狩りに使ってアルゴリズムを考えれば良いですね。

回答No.5

qntmphscs

＃１の補足の件ですが

> ａｂ各位の数字の０～９が同じにならないようにしたいのです。

０が並ぶことと切り離してよいならかんたんですが・・・

文字列型の変数aを確保。
整数型の配列n[9]を確保して

for(i=0;i<=9;i++){
n[i] = i;
}

で配列nに０～９を格納します。
もう一つフラグ用に整数型配列f[9]を確保して

for(i=0;i<=9;i++){
f[i] = 0;
}

と初期化しておきます。

ループ処理開始
　乱数で０～９を生成。
　fの全要素をスキャンして、f[乱数] = 0ならば
　　aの末尾にa[乱数]の値を連結。（言語によってキャストする必要あり）
　　f[乱数] = 1としてフラグを立てる。
　フラグが立っていれば何もしない。
ループ処理終了

ループの脱出条件はfの全要素の値が１になった時です。
これで文字列aに０～９を重複させずに格納できます。

計算に使う時は整数型にキャストすればいいでしょう。

さらに０が並ぶことと融合するには・・・

m = 0;
n = 0;
x = a;　（ａは整数型にキャスト済みと仮定）
y = a;

while(x mod 2 == 0){
x = x / 2;
m++;
}

while(y mod 5 == 0){
y = y / 5;
n++;
}

と類似のコードで2^m*5^nのm,nを拾う方法が考えられます。
ただ、この方法ではm,nを指定してaを生成することはできませんね。

お礼

ご丁寧なレスありがとうございます。
とても勉強になりました。
本当に、ありがとうございます。

回答No.4

elmclose

No.1 です。

>ａｂ各位の数字の０～９が同じにならないようにしたいのです。
>（ａはａの中で、ｂはｂの中でです）
こっちは難しいですね。なかなかエレガントな方法は思い付かないです。No.1で書いた方法と総当り的試行錯誤とを併用して、各位の数字が重複しないようなa,bを探すしかないのではないでしょうか。

お礼

レスありがとうございます。
やはり、そうですよね。

今まで自分は、
全てを総当り的試行錯誤でやろうとしていたので、
それに比べれば、とても良くなりそうです。
本当に、ありがとうございます。

回答No.3

qntmphscs

＃２、間違えました。maxではなくminです。

回答No.2

qntmphscs

932,640×18,750＝17,487,000,000を例にします。

932,640＝(2^5)*5*5829
18,750＝2*(5^5)*3

よって{(2^5)*5}*{2*(5^5)}＝(2^6)*(5^6)＝(10^6)

一方17,487,000,000＝17487*(10^6)

これでおわかりでしょう。アルゴリズムを組むなら

m、n、xをランダムな整数として生成して
2^m*5^n*x
を２回ループ、mとnの値を記憶しておけばmax(Σm,Σn)が０の個数を表します。

お礼

レスありがとうございます。
なるほど、やっと理解できました。
（理解に３０分以上かかってしまった．．．汗）

と同時に、ａｂの下の位をゼロにしたくなければ、
２を含む側と５を含む側とを、分けた方が良さそうだと気付きました。
本当に、ありがとうございます。