UVa 10799 - OOPS! They did it Again...

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在區間 [l, r] 中挑出 k 個數字,並且挑出數字的間隔要相同,總問總和為 k 個倍數有多少種。

Sample Input

1
2
3
4
5
1 10 4  
2 10 4
1 48 2
1222 2329228 2
0 0 0

Sample Output

1
2
3
4
Case 1: 4
Case 2: 3
Case 3: 552
Case 4: 1354902984009

Solution

首先,可以窮舉間隔 d 與首項 a,根據等差公式可以推導得到 $(2 a + (K - 1)d) K /2 = aK + (K - 1)d K /2$,為了使之成立,必須滿足 K 整除的需求。為了加速運算考慮只窮舉間隔 d,找到合法的 a 解區間。

即便這樣 d 的範圍仍然很大,再仔細觀察一下運算,解區間的解個數呈現等差,觀察後直接計算即可。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;

int main() {
long long L, R, K;
int cases = 0;
while (scanf("%lld %lld %lld", &L, &R, &K) == 3 && L + R + K) {
long long ret = 0, N = R - L;
// for (int d = 1; d <= N; d++) {
// if (K * (K-1) * d %2 == 0 && K * (K-1) * d / 2 % K == 0) {
// int ra0 = R - (K-1) * d, la0 = L;
// if (la0 <= ra0)
// ret += ra0 - la0 + 1, printf("%d\n", ra0 - la0 + 1);
// else
// break;
// }
// }

long long b0 = -1, bn = -1, bd = -1;
for (long long d = 1; d <= N/(K-1); d++) {
if (K * (K-1) * d %2 == 0 && K * (K-1) * d / 2 % K == 0) {
long long ra0 = R - (K-1) * d, la0 = L;
if (la0 <= ra0) {
if (b0 == -1)
b0 = ra0 - la0 + 1;
else {
bd = b0 - (ra0 - la0 + 1);
break;
}
}
}
}
for (long long d = N / (K-1); d >= 1; d--) {
if (K * (K-1) * d %2 == 0 && K * (K-1) * d / 2 % K == 0) {
long long ra0 = R - (K-1) * d, la0 = L;
if (la0 <= ra0) {
bn = ra0 - la0 + 1;
break;
}
}
}

if (b0 != -1) {
ret = (b0 + bn) * ((b0 - bn) / bd + 1)/2;
}
// printf("%lld %lld %lld\n", b0, bn, bd);
printf("Case %d: %lld\n", ++cases, ret);
}
return 0;
}
/*
1 20000000 10000000
1 20000000 100000
*/