解題區/解題區 - UVa

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
*/