回答編集履歴
2
バグ修正とコメント添削
answer
CHANGED
@@ -5,60 +5,87 @@
|
|
5
5
|
---
|
6
6
|
|
7
7
|
```java
|
8
|
-
static void
|
8
|
+
public static void main(String[] args) {
|
9
|
+
long start = System.currentTimeMillis();
|
9
10
|
|
10
|
-
int n = 0; //n //n個目(の三角数)
|
11
|
-
|
11
|
+
func(500);
|
12
|
-
int t = 0; //triangle //三角数
|
13
|
-
int d = 0; //divisors //三角数の約数の個数
|
14
12
|
|
13
|
+
long end = System.currentTimeMillis();
|
14
|
+
System.out.println((end - start) + "ms");
|
15
|
+
}
|
16
|
+
|
17
|
+
static void func(int num) {
|
18
|
+
|
19
|
+
int n = 0; //自然数n
|
20
|
+
int t = 0; //n番目の三角数(総和)
|
21
|
+
|
22
|
+
//約数の個数の性質「互いに素なaとbについて、
|
23
|
+
//a*bの約数の個数は、aの約数の個数×bの約数の個数に等しい」
|
24
|
+
//nとn+1は互いに素なのでnかn+1のどちらかが偶数になる
|
25
|
+
|
26
|
+
int x = 0; //(偶数奇数で分けて偶数の方を2で割る)
|
27
|
+
int y = 0; //(偶数奇数で分けて偶数の方を2で割る)
|
28
|
+
int d = 0; //分けて計算した約数の個数を掛けた総数
|
29
|
+
|
15
30
|
while (d < num) {
|
16
31
|
|
32
|
+
//自然数n
|
17
33
|
n++;
|
18
34
|
|
19
|
-
|
35
|
+
//三角数の公式
|
36
|
+
//n(n+1)/2
|
20
37
|
|
21
|
-
|
38
|
+
//n 1 2 3 4 5 6 7 8 9 10
|
39
|
+
//三角数 1 3 6 10 15 21 28 36 45 55
|
40
|
+
//約数 1 2 4 4 4 4 6 9 6 4
|
22
41
|
|
23
|
-
//「nとn+1のうち、偶数を2で割ったもの」
|
24
|
-
//
|
42
|
+
//偶数奇数判定
|
25
43
|
if (n % 2 == 0) {
|
26
|
-
|
44
|
+
x = n / 2;
|
45
|
+
y = n + 1;
|
27
46
|
} else {
|
47
|
+
x = n;
|
28
|
-
|
48
|
+
y = (n + 1) / 2;
|
29
49
|
}
|
50
|
+
|
51
|
+
//個別に約数の個数を求め掛け合わせて総数を求める
|
52
|
+
d = getD(x) * getD(y);
|
30
53
|
}
|
31
|
-
System.out.println("n:" + n + " t:" + t + " d:" + d);
|
32
|
-
System.out.println("Answer:" + t);
|
33
54
|
|
55
|
+
//ログ出力用
|
56
|
+
t = n * (n + 1) / 2;
|
57
|
+
|
58
|
+
System.out.print("last n:" + (n));
|
59
|
+
System.out.print(" t:" + t);
|
60
|
+
System.out.print(" d:" + d);
|
61
|
+
System.out.println();
|
62
|
+
System.out.println("Ans:" + t);
|
34
63
|
}
|
35
64
|
|
36
|
-
//
|
65
|
+
//約数の個数を求める
|
37
|
-
//範囲は三角数の平方根まで
|
38
|
-
//三角数が平方数の場合は+1する
|
39
|
-
static int
|
66
|
+
static int getD(final int t) {
|
40
67
|
|
41
|
-
int
|
68
|
+
int d = 0;
|
42
|
-
int rootT = (int) Math.sqrt(triangle);
|
43
69
|
|
70
|
+
final int rootT = (int) Math.sqrt(t);
|
71
|
+
|
44
72
|
for (int i = 1; i <= rootT; i++) {
|
45
|
-
if (
|
73
|
+
if (t % i == 0) {
|
46
|
-
|
74
|
+
d++;
|
47
75
|
}
|
48
76
|
}
|
49
|
-
divisors = divisors * 2;
|
50
77
|
|
78
|
+
d *= 2;
|
79
|
+
|
51
|
-
if (
|
80
|
+
if (t == rootT * rootT) {
|
52
|
-
|
81
|
+
d--;
|
53
82
|
}
|
83
|
+
|
54
|
-
return
|
84
|
+
return d;
|
55
85
|
}
|
56
|
-
|
57
86
|
```
|
58
87
|
出力結果
|
59
88
|
---
|
60
|
-
n:12375 t:76576500 d:576
|
89
|
+
last n:12375 t:76576500 d:576
|
61
|
-
|
90
|
+
Ans:76576500
|
62
|
-
|
91
|
+
0ms
|
63
|
-
|
64
|
-
(307ms※平方根までの処理を実装前の結果)
|
1
未実装の修正を追加
answer
CHANGED
@@ -1,49 +1,64 @@
|
|
1
1
|
頂いたアドバイスで作り直したところ、かなり改善できました。
|
2
2
|
ありがとうございました。
|
3
|
+
※追加で平方根の処理を実装したところ更に改善できました。
|
3
4
|
|
4
5
|
---
|
5
6
|
|
6
7
|
```java
|
7
8
|
static void func2(int num) {
|
8
|
-
|
9
|
+
|
9
10
|
int n = 0; //n //n個目(の三角数)
|
10
|
-
int n1= 0;
|
11
|
+
int n1 = 0; //n+1 //n+1
|
11
12
|
int t = 0; //triangle //三角数
|
12
|
-
int d = 0;
|
13
|
+
int d = 0; //divisors //三角数の約数の個数
|
13
|
-
|
14
|
-
while(d < num) {
|
15
14
|
|
15
|
+
while (d < num) {
|
16
|
+
|
16
17
|
n++;
|
17
18
|
|
18
|
-
n1 = n+1;
|
19
|
+
n1 = n + 1;
|
19
|
-
|
20
|
+
|
20
|
-
t = n*n1/2;
|
21
|
+
t = n * n1 / 2; //三角数の公式 n(n+1)/2
|
21
|
-
|
22
|
+
|
22
23
|
//「nとn+1のうち、偶数を2で割ったもの」
|
23
24
|
// 奇数偶数で分けて計算して掛ける
|
24
|
-
if(n % 2 == 0) {
|
25
|
+
if (n % 2 == 0) {
|
25
|
-
d = getDivisors(n/2) * getDivisors(n1)
|
26
|
+
d = getDivisors(n / 2) * getDivisors(n1);
|
26
27
|
} else {
|
27
|
-
d = getDivisors(n) * getDivisors(n1/2)
|
28
|
+
d = getDivisors(n) * getDivisors(n1 / 2);
|
28
29
|
}
|
29
30
|
}
|
30
|
-
System.out.println("n:"+n+" t:"+t+" d:"+
|
31
|
+
System.out.println("n:" + n + " t:" + t + " d:" + d);
|
32
|
+
System.out.println("Answer:" + t);
|
33
|
+
|
31
34
|
}
|
32
|
-
|
35
|
+
|
33
|
-
//約数の個数を求める
|
36
|
+
//三角数の約数の個数を求める
|
37
|
+
//範囲は三角数の平方根まで
|
38
|
+
//三角数が平方数の場合は+1する
|
34
39
|
static int getDivisors(int triangle) {
|
35
|
-
|
40
|
+
|
36
41
|
int divisors = 0;
|
42
|
+
int rootT = (int) Math.sqrt(triangle);
|
43
|
+
|
37
|
-
for (int i = 1; i <=
|
44
|
+
for (int i = 1; i <= rootT; i++) {
|
38
45
|
if (triangle % i == 0) {
|
39
46
|
divisors++;
|
40
47
|
}
|
41
48
|
}
|
49
|
+
divisors = divisors * 2;
|
50
|
+
|
51
|
+
if (triangle == rootT * rootT) {
|
52
|
+
divisors++;
|
53
|
+
}
|
42
54
|
return divisors;
|
43
55
|
}
|
56
|
+
|
44
57
|
```
|
45
58
|
出力結果
|
46
59
|
---
|
47
60
|
n:12375 t:76576500 d:576
|
48
61
|
Answer:76576500
|
49
|
-
|
62
|
+
7ms
|
63
|
+
|
64
|
+
(307ms※平方根までの処理を実装前の結果)
|