题目大意
已知一个三角形的周长\(n\)，三角形的边长是整数，求三角形的边长有多少种可能。
\(1\le n \le 10^{18}\)
分析
猜想答案应该是组合数的运算，存在某种规律。
实现
首先，我们通过暴力打表，枚举出周长\(\le100\)时的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| C num
1 0
2 0
3 1
4 0
+ 1
5 1
6 1
7 2
8 1
+ 2
9 3
10 2
11 4
12 3
+ 2
13 5
14 4
15 7
16 5
+ 3
17 8
18 7
19 10
20 8
+ 4
21 12
22 10
23 14
24 12
+ 4
25 16
26 14
27 19
28 16
+ 5
29 21
30 19
31 24
32 21
+ 6
33 27
34 24
35 30
36 27
+ 6
37 33
38 30
39 37
40 33
+ 7
41 40
42 37
43 44
44 40
+ 8
45 48
46 44
47 52
48 48
+ 8
49 56
50 52
51 61
52 56
+ 9
53 65
54 61
55 70
56 65
+ 10
57 75
58 70
59 80
60 75
+ 10
61 85
62 80
63 91
64 85
+ 11
65 96
66 91
67 102
68 96
+ 12
69 108
70 102
71 114
72 108
+ 12
73 120
74 114
75 127
76 120
+ 13
77 133
78 127
79 140
80 133
81 147
82 140
83 154
84 147
85 161
86 154
87 169
88 161
89 176
90 169
91 184
92 176
93 192
94 184
95 200
96 192
97 208
98 200
99 217
100 208
|
非常神奇地，发现可以每四个分成一组，首尾一致。进一步观察，每组第一个数与下一组第一个数的差为2 2 3 4 4 5 6 6 7 8 8 9 ...最终得出结论：每组12个数，最后一个数构成以6为公差的二阶等差数列。于是使用二阶等差数列第\(n\)项公式可以求出每组最后一个数： \[
a_n=a_1+(n-1)\times(a_2-a_1)+\frac{(n-2)(n-1)}{2}\times d
\] 接下来继续观察，发现以每十二个数为一组的数列中存在如下规律：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| ll p = n / 12;
ll num12 = f1(p + 2);
ll gongcha = f2(p + 1);
gongcha -= 1;
gongcha /= 3;
num[11] = num12;
num[8] = num12;
num[9] = num12 - gongcha / 2;
num[10] = num[9] + gongcha + 1;
num[7] = num[8] - gongcha - 1;
num[4] = num[7];
num[5] = num[4] - gongcha / 2;
num[6] = num[5] + gongcha + 1;
num[3] = num[4] - gongcha;
num[0] = num[3];
num[1] = num[0] - gongcha / 2;
num[2] = num[1] + gongcha;
|
最后附完整代码（\(0ms,260kb\)）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, ma1 = 1, mb1 = 7, d = 6;
const ll mod = 1e9 + 7;
ll f1(ll x) {
ll p;
if (x % 2 == 0) {
p = (x - 2) / 2;
p %= mod;
p *= (x - 1) % mod;
} else {
p = (x - 1) / 2;
p %= mod;
p *= (x - 2) % mod;
}
return ma1 % mod + (x - 1) * mb1 % mod + p * d;
}
ll f2(ll x) {
return 7 + (x - 1) * 6;
}
ll num[13];
ll xiao[9] = {0, 0, 0, 1, 0, 1, 1, 2, 1};
int main() {
cin >> n;
if (n < 9) {
cout << xiao[n];
return 0;
}
n -= 9;
ll p = n / 12;
ll m = n - p * 12;
ll num12 = f1(p + 2);
ll gongcha = f2(p + 1);
gongcha -= 1;
gongcha /= 3;
num[11] = num12;
num[8] = num12;
num[9] = num12 - gongcha / 2;
num[10] = num[9] + gongcha + 1;
num[7] = num[8] - gongcha - 1;
num[4] = num[7];
num[5] = num[4] - gongcha / 2;
num[6] = num[5] + gongcha + 1;
num[3] = num[4] - gongcha;
num[0] = num[3];
num[1] = num[0] - gongcha / 2;
num[2] = num[1] + gongcha;
cout << num[m] % mod;
return 0;
}
|