どの桁にも0が含まれない10000桁の正の整数Pがある。aを超えない最大の整数を[a]と表すとき、P以下の正の整数Qに対して[P/Q]に含まれる0の数の最大値を求めよ。
どう手をつけたらいいのかさっぱりです。
よろしくお願いします。
|
No.34390 - 2015/11/22(Sun) 01:38:29
| ☆ Re: 最大値 / IT | | | Ｐは固定でＱが１からＰまで動くときの最大値、ということでしょうか？
Ｐも任意ということなら
Ｐ=11111111.....1,Ｑ=111..1のようなとき最大になりそうな気がします。(出来てませんが）
|
No.34394 - 2015/11/22(Sun) 07:53:17 |
| ☆ Re: 最大値 / ウシ | | | 0を含まない10000桁のPをQで割ったときの商の整数部分の各桁に含まれる0の個数のとりうる最大値ということではないかと思うのですが・・・。
|
No.34395 - 2015/11/22(Sun) 08:32:06 |
| ☆ Re: 最大値 / IT | | | 初心に帰って、筆算で１万桁の整数を3桁や4桁の整数で割るとき
商がどうなるか考えてみると見えてくるかも知れませんね。
もちろん最後まで計算することはできません。
何桁になるかと、商の０以外の最初の２桁ぐらいを考えるだけでいいです。
|
No.34402 - 2015/11/22(Sun) 17:57:28 |
| ☆ Re: 最大値 / IT | | | 例えばQが4桁の場合(1000≦Q＜10000)
a00000b......のように0が５桁並ぶ数にQを掛けても
0の桁が少なくとも１つは残ることが分かります。
このことを使えばQがn桁の場合の[P/Q]に含まれる0の数が上から押さえられると思います。
上から押さえる数Mが最大になるようなnを見つけて
さらに、[P/Q]に含まれる0の数がMになるようなP,Qを具体的に示せばいいと思います。
|
No.34426 - 2015/11/23(Mon) 09:37:27 |
| ☆ Re: 最大値 / 冬支度 | | | P/Q=a[1]10^b[1]+a[2]10^b[2]+…+a[N]10^b[N]+C
(1≦a[1],a[2],…,a[N]≦9,0≦b[N]<b[N-1]<…<b[1],0≦C<1)とおくと、
10^9999≦P<10^10000
Qの桁数をk(1≦k≦10000)とすると
10^k-1≦Q<10^kより
b[1]≦10000-k
また
1≦m≦N-1となる正の整数mについてb[m]-b[m+1]≦k+1 …?@
b[N]≦k …?A
ここで、P/Qの整数部分の0である桁の個数はb[1]+1-N
?@より
b[1]-b[2]≦k+1,b[2]-b[3]≦k+1,・・・,b[N-1]-b[N]≦k+1
これらの辺々をたしあわせて
b[1]-b[N]≦(N-1)(k+1)
ゆえに b[1]≦(N-1)(k+1)+b[N]
?Aより
b[1]≦(N-1)(k+1)+k=(k+1)N-1
よって
(b[1]+1)/(k+1)≦N
したがって
b[1]+1-N≦b[1]+1-(b[1]+1)/(k+1)=(kb[1]-1)/(k+1)+1≦{k(10000-k)-1}/(k+1)+1=10003-{(k+1)+10002/(k+1)}≦10003-2√(10002)<9803
よって
[P/Q]に含まれうる0の数の最大値は
9802
です。
|
No.34435 - 2015/11/23(Mon) 19:26:50 |
|
