回答編集履歴
6
修正
answer
CHANGED
|
@@ -28,4 +28,4 @@
|
|
|
28
28
|
|
|
29
29
|
### 追記
|
|
30
30
|
|
|
31
|
-
多倍長演算の乗算は必要ないかもしれません。3 は 2 進数で 11 なので、何かに 3 をかけるということは、その数を左に 1 ビットシフトしたものとその数自身を足したものに等しくなります。ビットシフトと加算を 165 回繰り返すだけなので、十分高速に結果が求まると思います。また、3 にビットシフトを 164 回繰り返すと
|
|
31
|
+
多倍長演算の乗算は必要ないかもしれません。3 は 2 進数で 11 なので、何かに 3 をかけるということは、その数を左に 1 ビットシフトしたものとその数自身を足したものに等しくなります。ビットシフトと加算を 165 回繰り返すだけなので、十分高速に結果が求まると思います。また、3 にビットシフトを 164 回繰り返すと 166 ビットなので、そこに加算した繰上りを入れても 167 ビットつまり 21 バイトに収まります。バッファは計算しながら動的に確保しなくても、21 バイト固定で間に合うはずです。後の問題はそれを 10 進数に直す際の除算ですね。しかしここまで十分高速に計算できているので、間に合いそうな気がします。
|
5
追記
answer
CHANGED
|
@@ -24,4 +24,8 @@
|
|
|
24
24
|
|
|
25
25
|
多倍長演算を用いて 3 を 165 回乗算すれば解は求まるわけですが、これを更に短縮しましょう。例えば p(3, 4) は真正直に 3 を 4 回乗算しなくても、p(p(3, 2), 2) で求められます。指数法則をうまく使って答えを導き出してください。
|
|
26
26
|
|
|
27
|
-
[指数法則 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%86%AA%E4%B9%97#%E6%8C%87%E6%95%B0%E6%B3%95%E5%89%87)
|
|
27
|
+
[指数法則 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%86%AA%E4%B9%97#%E6%8C%87%E6%95%B0%E6%B3%95%E5%89%87)
|
|
28
|
+
|
|
29
|
+
### 追記
|
|
30
|
+
|
|
31
|
+
多倍長演算の乗算は必要ないかもしれません。3 は 2 進数で 11 なので、何かに 3 をかけるということは、その数を左に 1 ビットシフトしたものとその数自身を足したものに等しくなります。ビットシフトと加算を 165 回繰り返すだけなので、十分高速に結果が求まると思います。また、3 にビットシフトを 164 回繰り返すと 165 ビットなので、そこに加算した繰上りを入れても 166 ビットつまり 21 バイトに収まります。バッファは計算しながら動的に確保しなくても、21 バイト固定で間に合うはずです。後の問題はそれを 10 進数に直す際の除算ですね。しかしここまで十分高速に計算できているので、間に合いそうな気がします。
|
4
修正
answer
CHANGED
|
@@ -10,7 +10,7 @@
|
|
|
10
10
|
|
|
11
11
|
話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(3, 10)) なので、これを代入すると x = p(3, t) = p(p(3, l(3, 10)), d) となります。
|
|
12
12
|
|
|
13
|
-
冪乗の指数法則より、p(3, t) = p(3, l(3, 10) * d) が成り立つため、t = l(3, 10) * d となります。ここで l(3, 10) は定数約 2.09590327428938 であり、d = t / l(3, 10) が成り立ちます。ここで
|
|
13
|
+
冪乗の指数法則より、p(3, t) = p(3, l(3, 10) * d) が成り立つため、t = l(3, 10) * d となります。ここで l(3, 10) は定数約 2.09590327428938 であり、d = t / l(3, 10) が成り立ちます。ここで d に n を代入することにより、t = n * 2.09590327428938 で求めることができます。
|
|
14
14
|
|
|
15
15
|
結論として、実数 a の小数点以下を切り捨てる架空の関数 int を考えた時、求める数は p(3, int(n * 2.09590327428938)) です。
|
|
16
16
|
|
3
修正
answer
CHANGED
|
@@ -10,7 +10,7 @@
|
|
|
10
10
|
|
|
11
11
|
話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(3, 10)) なので、これを代入すると x = p(3, t) = p(p(3, l(3, 10)), d) となります。
|
|
12
12
|
|
|
13
|
-
冪乗の指数法則より、p(3, t) = p(3, l(3, 10) * d) が成り立つため、t = l(3, 10) * d となります。ここで l(3, 10) は定数約 2.09590327428938 であり、d = t / l(3, 10) が成り立ちます。ここで
|
|
13
|
+
冪乗の指数法則より、p(3, t) = p(3, l(3, 10) * d) が成り立つため、t = l(3, 10) * d となります。ここで l(3, 10) は定数約 2.09590327428938 であり、d = t / l(3, 10) が成り立ちます。ここで t に n を代入することにより、d = n * 2.09590327428938 で求めることができます。
|
|
14
14
|
|
|
15
15
|
結論として、実数 a の小数点以下を切り捨てる架空の関数 int を考えた時、求める数は p(3, int(n * 2.09590327428938)) です。
|
|
16
16
|
|
2
修正
answer
CHANGED
|
@@ -8,15 +8,15 @@
|
|
|
8
8
|
|
|
9
9
|
なぜ 10 を底とする冪を考えるかというと、これで 10 進数における桁数が求められるからです。例えば 1 は p(10, 0) であり、10 は p(10, 1) であり、100 は p(10, 2) です。よって、冪が一桁である時、指数は 0 以上 1 未満となり、二桁である時、1 以上 2 未満、三桁である時、2 以上 3 未満となります。たとえば二桁の数 50 が冪の時、指数は約 1.69897000433602 となり、p(10, 1.69897000433602) ≒ 50, l(10, 50) ≒ 1.69897000433602 となります。
|
|
10
10
|
|
|
11
|
-
話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(
|
|
11
|
+
話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(3, 10)) なので、これを代入すると x = p(3, t) = p(p(3, l(3, 10)), d) となります。
|
|
12
12
|
|
|
13
|
-
冪乗の指数法則より、p(3, t) = p(3, l(
|
|
13
|
+
冪乗の指数法則より、p(3, t) = p(3, l(3, 10) * d) が成り立つため、t = l(3, 10) * d となります。ここで l(3, 10) は定数約 2.09590327428938 であり、d = t / l(3, 10) が成り立ちます。ここで d に n を代入することにより、t = n * 2.09590327428938 で求めることができます。
|
|
14
14
|
|
|
15
|
-
結論として、実数 a の小数点以下を切り捨てる架空の関数 int を考えた時、求める数は p(3, int(n
|
|
15
|
+
結論として、実数 a の小数点以下を切り捨てる架空の関数 int を考えた時、求める数は p(3, int(n * 2.09590327428938)) です。
|
|
16
16
|
|
|
17
17
|
### n = 79 の時の 3 の累乗の最大値
|
|
18
18
|
|
|
19
|
-
p(3, int(79
|
|
19
|
+
p(3, int(79 × 2.09590327428938)) = p(3, 165) = 5308930362839928667688049530226627139643793175493798707037516219525092562313843
|
|
20
20
|
|
|
21
21
|
が答えになります。
|
|
22
22
|
|
1
修正
answer
CHANGED
|
@@ -6,7 +6,7 @@
|
|
|
6
6
|
|
|
7
7
|
3 の累乗である n 桁の最大値 x は 3 を底とする冪なので、p(3, t) で表すことができます。また、これを 10 を底とする冪と考えると、p(10, d) で表すこともできます。x = p(3, t) = p(10, d) です。
|
|
8
8
|
|
|
9
|
-
なぜ 10 を底とする冪を考えるかというと、これで 10 進数における桁数が求められるからです。例えば
|
|
9
|
+
なぜ 10 を底とする冪を考えるかというと、これで 10 進数における桁数が求められるからです。例えば 1 は p(10, 0) であり、10 は p(10, 1) であり、100 は p(10, 2) です。よって、冪が一桁である時、指数は 0 以上 1 未満となり、二桁である時、1 以上 2 未満、三桁である時、2 以上 3 未満となります。たとえば二桁の数 50 が冪の時、指数は約 1.69897000433602 となり、p(10, 1.69897000433602) ≒ 50, l(10, 50) ≒ 1.69897000433602 となります。
|
|
10
10
|
|
|
11
11
|
話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(10, 3)) なので、これを代入すると x = p(3, t) = p(p(3, l(10, 3)), d) となります。
|
|
12
12
|
|