回答編集履歴
2
ちょっと読みやすく…なったのかなー
test
CHANGED
|
@@ -4,37 +4,37 @@
|
|
|
4
4
|
|
|
5
5
|
|
|
6
6
|
|
|
7
|
-
1. `N=A×B`(`A≦B`)
|
|
7
|
+
1. `N = A×B`(`A ≦ B`)
|
|
8
8
|
|
|
9
9
|
として`√N`(Nの平方根)を考えます。
|
|
10
10
|
|
|
11
|
-
`A≦B`より両辺に`N`をかけて
|
|
11
|
+
`A ≦ B`より両辺に`N`をかけて
|
|
12
12
|
|
|
13
|
-
2. `A×N≦B×N`
|
|
13
|
+
2. `A×N ≦ B×N`
|
|
14
14
|
|
|
15
|
-
`N=A×B`だから
|
|
15
|
+
`N = A×B`だから
|
|
16
16
|
|
|
17
|
-
3. `A×A×B≦B×N`
|
|
17
|
+
3. `A×A×B ≦ B×N`
|
|
18
18
|
|
|
19
|
-
4. `A^2×B≦N×B` ※ ^2は2乗を表す
|
|
19
|
+
4. `A^2×B ≦ N×B` ※ ^2は2乗を表す
|
|
20
20
|
|
|
21
21
|
`B`は0ではない正の整数なので両辺を`N`で割って
|
|
22
22
|
|
|
23
|
-
5. `A^2≦N`
|
|
23
|
+
5. `A^2 ≦ N`
|
|
24
24
|
|
|
25
25
|
両辺の正の平方根を求めて
|
|
26
26
|
|
|
27
|
-
6. `A≦√N` ※ √は平方根を表す。
|
|
27
|
+
6. `A ≦ √N` ※ √は平方根を表す。
|
|
28
28
|
|
|
29
29
|
Bもどうように、
|
|
30
30
|
|
|
31
|
-
7. `B≧√N`
|
|
31
|
+
7. `B ≧ √N`
|
|
32
32
|
|
|
33
33
|
となることがわかります。
|
|
34
34
|
|
|
35
35
|
|
|
36
36
|
|
|
37
|
-
全ての`F(A, B)`の組合せは`A≦B`の時は上の規則に従います。また`F(A, B)=F(B, A)`ですので、実際に確認するのは`A≦B`の時だけです。このなから`F(A, B)`が最小になるものを探せば良いとなります。
|
|
37
|
+
全ての`F(A, B)`の組合せは`A ≦ B`の時は上の規則に従います。また`F(A, B) = F(B, A)`ですので、実際に確認するのは`A ≦ B`の時だけです。このなから`F(A, B)`が最小になるものを探せば良いとなります。
|
|
38
38
|
|
|
39
39
|
|
|
40
40
|
|
|
@@ -42,33 +42,33 @@
|
|
|
42
42
|
|
|
43
43
|
|
|
44
44
|
|
|
45
|
-
1. `N=Ai×Bi=Aj×Bj`(`Ai
|
|
45
|
+
1. `N = Ai×Bi = Aj×Bj`(`Ai < Aj`)
|
|
46
46
|
|
|
47
|
-
としたとき、`Ai
|
|
47
|
+
としたとき、`Ai < Aj`より両辺に`Bj`をかけて
|
|
48
48
|
|
|
49
|
-
2. `Ai×Bj
|
|
49
|
+
2. `Ai×Bj < Aj×Bj = N = Ai×Bi`
|
|
50
50
|
|
|
51
51
|
つまり、
|
|
52
52
|
|
|
53
|
-
3. `Ai×Bj
|
|
53
|
+
3. `Ai×Bj < Ai×Bi`
|
|
54
54
|
|
|
55
55
|
`Ai`は正の整数なので`Ai`を両辺で割って
|
|
56
56
|
|
|
57
|
-
4. `Bj
|
|
57
|
+
4. `Bj < Bi`
|
|
58
58
|
|
|
59
|
-
ここで`F(A, B)`は`A`より`B`の方が大きいので`B`によってのみ決まります。また、大きい数字の方が桁数は
|
|
59
|
+
ここで`F(A, B)`は`A`より`B`の方が大きいので`B`によってのみ決まります。また、大きい数字の方が桁数は大きくなりますので、
|
|
60
60
|
|
|
61
|
-
5. `F(Aj, Bj)≦F(Ai, Bi)`
|
|
61
|
+
5. `F(Aj, Bj) ≦ F(Ai, Bi)`
|
|
62
62
|
|
|
63
63
|
が成り立ちます。
|
|
64
64
|
|
|
65
65
|
|
|
66
66
|
|
|
67
|
-
`F(A, B)`の組は最小を求めるのですから、ある`Aj`と`F(Aj, Bj)`があるなら、`Aj`より小さい`Ai`のときの`F(Ai, Bi)`の桁がそれより小さくなることはありません。以上のことから`N=A×B`(`A≦B`)の組合せで`A`が最大の物を求めれば良いとなります。
|
|
67
|
+
`F(A, B)`の組は最小を求めるのですから、ある`Aj`と`F(Aj, Bj)`があるなら、`Aj`より小さい`Ai`のときの`F(Ai, Bi)`の桁がそれより小さくなることはありません。以上のことから`N = A×B`(`A ≦ B`)の組合せで`A`が最大の物を求めれば良いとなります。
|
|
68
68
|
|
|
69
69
|
|
|
70
70
|
|
|
71
|
-
最初に戻って`A≦√N`でした。つまり、`√N`から順番に**1ずつ減らしながら**該当する**最大の**`A`を求めればいいと言うことです。該当するかどうかは`N`を`A`で割った時の余りが0になるかどうかでわかります。`A`が求まれば`N÷A`で`B`が求まるので、その桁数を数えるだけとなります。
|
|
71
|
+
最初に戻って`A ≦ √N`でした。つまり、`√N`から順番に**1ずつ減らしながら**該当する**最大の**`A`を求めればいいと言うことです。該当するかどうかは`N`を`A`で割った時の余りが0になるかどうかでわかります。`A`が求まれば`N÷A`で`B`が求まるので、その桁数を数えるだけとなります。
|
|
72
72
|
|
|
73
73
|
|
|
74
74
|
|
1
補足追加
test
CHANGED
|
@@ -77,3 +77,13 @@
|
|
|
77
77
|
|
|
78
78
|
|
|
79
79
|
最悪計算量はO(√n)です。
|
|
80
|
+
|
|
81
|
+
|
|
82
|
+
|
|
83
|
+
---
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
【補足】
|
|
88
|
+
|
|
89
|
+
`√N`から増やしていく場合は最悪が`N-√N`回になり、計算量がO(n)のままなので、言語によっては間に合いません(少なくともRubyはTLEだった)。Nが素数の場合だけ別にするというのも2000000014(2×1000000007)とかがあるので、間に合わないと思われます。
|