teratail
回答率
85.48%
質問するログイン新規登録
トップJavaに関する質問このコードの処理をどうにかして速くしたいです

編集履歴

回答編集履歴

3

いろいろボロボロだったので再投稿

2017/04/01 14:13

投稿

swordone
swordone

スコア20651

test CHANGED
@@ -10,87 +10,109 @@
10
10
 
11
11
  ```java
12
12
 
13
- public minF(int n) {
13
+ public class Q70846 {
14
-
15
- int balance = 1; // 素因数を均等に分けた際の片方
16
-
17
- int restMulti = 1; // ペアにならず残った素因数の積
18
-
19
- List<Integer> prime = new ArrayList<>();
20
-
21
- for (int i = 2; i * i <= n; i++) {
22
-
23
- boolean rest = false; // その素因数がペアにならず残っているか
24
-
25
- while (n % i == 0) {
26
-
27
- n /= i;
28
-
29
- if (rest) balance *= i; // 素因数のペア成立時、均等に分ける
30
-
31
- rest = !rest;
32
-
33
- }
34
-
35
- if (rest) {
36
-
37
- prime.add(i);
38
-
39
- restMulti *= i;
40
-
41
- }
42
-
43
- }
44
-
45
- if (n != 1) {
46
-
47
- prime.add(n);
48
-
49
- restMulti *= n;
50
-
51
- }
52
14
 
53
15
 
54
16
 
55
- // 余った素因数がなかった場合、nは平方数ということになり、
17
+ public static void main(String[] args) {
56
18
 
57
- // 均等に分けたbalanceが平方根となり最小の桁数
19
+ try (Scanner sc = new Scanner(System.in)) {
58
20
 
59
- if(prime.isEmpty()) {
21
+ System.out.println(minF(sc.nextInt()));
60
22
 
61
- return (int)Math.log10(balance) + 1;
23
+ }
62
24
 
63
- }
25
+ }
64
26
 
65
27
 
66
28
 
67
- // 素因数をなるべく均等になるように分配する分け方を探す
29
+ public static int minF(int n) {
68
30
 
69
- // 重複がないよう、primeの0番が入る組と入らない組に分ける
31
+ int balance = 1; // 素因数を均等に分けた際の片方
70
32
 
71
- int minB = Integer.MAX_VALUE; // N = A*B(A≦B)となる最小のB
33
+ int restMulti = 1; // ペアにならず残った素因数の積
72
34
 
73
- for (int i = 2; i <= (1 << prime.size()); i += 2) {
35
+ List<Integer> prime = new ArrayList<>();
74
36
 
75
- BitSet set = BitSet.ValueOf(new long[]{i});
37
+ for (int i = 2; i * i <= n; i++) {
76
38
 
77
- int a = 1;
39
+ boolean rest = false; // その素因数がペアにならず残っているか
78
40
 
79
- for (j = set.nextSetBit(0); j >= 0; j = set.nextSetBit(j + 1)) {
41
+ while (n % i == 0) {
80
42
 
81
- a *= prime.get(j);
43
+ n /= i;
82
44
 
83
- }
45
+ if (rest) balance *= i; // 素因数のペア成立時、均等に分ける
84
46
 
85
- int b = restMulti / a;
47
+ rest = !rest;
86
48
 
87
- minB = Math.min(minA, Math.max(a, b));
49
+ }
88
50
 
89
- }
51
+ if (rest) {
90
52
 
53
+ prime.add(i);
54
+
55
+ restMulti *= i;
56
+
57
+ }
58
+
59
+ }
60
+
61
+ if (n != 1) {
62
+
63
+ prime.add(n);
64
+
65
+ restMulti *= n;
66
+
67
+ }
68
+
69
+
70
+
71
+ // 余った素因数がなかった場合、nは平方数ということになり、
72
+
73
+ // 均等に分けたbalanceが平方根となり最小の桁数
74
+
75
+ if(prime.isEmpty()) {
76
+
77
+ return (int)Math.log10(balance) + 1;
78
+
79
+ }
80
+
81
+
82
+
83
+ // 素因数をなるべく均等になるように分配する分け方を探す
84
+
85
+ // 重複がないよう、primeの0番が入る組と入らない組に分ける
86
+
87
+ int minB = Integer.MAX_VALUE; // N = A*B(A≦B)となる最小のB
88
+
89
+ for (int i = 2; i <= (1 << (prime.size() - 1)); i += 2) {
90
+
91
+ BitSet set = BitSet.valueOf(new long[]{i});
92
+
93
+ int a = 1;
94
+
95
+ for (int j = set.nextSetBit(0); j >= 0; j = set.nextSetBit(j + 1)) {
96
+
97
+ a *= prime.get(j);
98
+
99
+ }
100
+
101
+ int b = restMulti / a;
102
+
103
+ minB = Math.min(minB, Math.max(a, b));
104
+
105
+ }
106
+
91
- return (int)Math.log10(minB) + 1
107
+ return (int)Math.log10(minB) + 1;
108
+
109
+ }
110
+
111
+
92
112
 
93
113
  }
114
+
115
+
94
116
 
95
117
  ```
96
118
 

2

素因数分解を利用したコード

2017/04/01 14:13

投稿

swordone
swordone

スコア20651

test CHANGED
@@ -3,3 +3,101 @@
3
3
  N=A×Bを満たしながら動くことを考えると、例えばN=8100の時、1×8100のように一方に偏るより、90×90のように均等に分かれたほうが小さくなります。そしてこの均等な状態から少しずれようものなら、一方が3桁になっていまい、最小ではなくなります。
4
4
 
5
5
  つまり、AとBはなるべく均等であるべきという結論になります。なので1という端の値は最終候補になります。
6
+
7
+
8
+
9
+ これをもとに、「Nの素因数を均等に分ける」と考えて組んでみたのが次のコード(未検証)。
10
+
11
+ ```java
12
+
13
+ public minF(int n) {
14
+
15
+ int balance = 1; // 素因数を均等に分けた際の片方
16
+
17
+ int restMulti = 1; // ペアにならず残った素因数の積
18
+
19
+ List<Integer> prime = new ArrayList<>();
20
+
21
+ for (int i = 2; i * i <= n; i++) {
22
+
23
+ boolean rest = false; // その素因数がペアにならず残っているか
24
+
25
+ while (n % i == 0) {
26
+
27
+ n /= i;
28
+
29
+ if (rest) balance *= i; // 素因数のペア成立時、均等に分ける
30
+
31
+ rest = !rest;
32
+
33
+ }
34
+
35
+ if (rest) {
36
+
37
+ prime.add(i);
38
+
39
+ restMulti *= i;
40
+
41
+ }
42
+
43
+ }
44
+
45
+ if (n != 1) {
46
+
47
+ prime.add(n);
48
+
49
+ restMulti *= n;
50
+
51
+ }
52
+
53
+
54
+
55
+ // 余った素因数がなかった場合、nは平方数ということになり、
56
+
57
+ // 均等に分けたbalanceが平方根となり最小の桁数
58
+
59
+ if(prime.isEmpty()) {
60
+
61
+ return (int)Math.log10(balance) + 1;
62
+
63
+ }
64
+
65
+
66
+
67
+ // 素因数をなるべく均等になるように分配する分け方を探す
68
+
69
+ // 重複がないよう、primeの0番が入る組と入らない組に分ける
70
+
71
+ int minB = Integer.MAX_VALUE; // N = A*B(A≦B)となる最小のB
72
+
73
+ for (int i = 2; i <= (1 << prime.size()); i += 2) {
74
+
75
+ BitSet set = BitSet.ValueOf(new long[]{i});
76
+
77
+ int a = 1;
78
+
79
+ for (j = set.nextSetBit(0); j >= 0; j = set.nextSetBit(j + 1)) {
80
+
81
+ a *= prime.get(j);
82
+
83
+ }
84
+
85
+ int b = restMulti / a;
86
+
87
+ minB = Math.min(minA, Math.max(a, b));
88
+
89
+ }
90
+
91
+ return (int)Math.log10(minB) + 1
92
+
93
+ }
94
+
95
+ ```
96
+
97
+
98
+
99
+ この方法のメリットとしては、raccyさんが出した2000000014(2×1000000007)のような極端な例の場合でも、素因数分解の仕組み上、√2000000014≒44721から目的の数2までたどるループ数よりも、素因数分解が完了するループ数√1000000007≒31623のほうがループ回数が少なくなります。(このケースで後半の素因数の組み合わせのチェックは1回しか起きないので、結果的にこちらのほうが少なくはなるが微差か)
100
+
101
+
102
+
103
+ デメリットとしては、素因数分解で孤立した素因数が多くなると、組み合わせチェックが多くなってしまうというのは考えられます。

1

訂正

2017/04/01 13:47

投稿

swordone
swordone

スコア20651

test CHANGED
@@ -2,4 +2,4 @@
2
2
 
3
3
  N=A×Bを満たしながら動くことを考えると、例えばN=8100の時、1×8100のように一方に偏るより、90×90のように均等に分かれたほうが小さくなります。そしてこの均等な状態から少しずれようものなら、一方が3桁になっていまい、最小ではなくなります。
4
4
 
5
- つまり、AとBはなるべく均等であるべきという結論になります。なので1とかの端の値は最初から検討する必要がありません。
5
+ つまり、AとBはなるべく均等であるべきという結論になります。なので1という端の値は最終候補になります。