hduoj 6672 Seq - 百度之星 2019

目录

1. 题目描述
   1. Problem Description
   2. Input
   3. Output
   4. Sample Input
   5. Sample Output
   6. Source
2. 解答

题目描述

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description

度度熊有一个递推式

$$
a_n = (\sum_{i=1}^{n-1}{a_i \times i})\ \% \ n其中 a1=1。现给出 n，需要求 an。
$$

其中 a1=1。现给出 n，需要求 an。

Input

第一行输入一个整数 T，代表 T (1≤T≤100000) 组数据。
接下 T 行，每行一个数字 n (1≤n≤1012)。

Output

输出 T 行，每行一个整数表示答案。

Sample Input

5
1
2
3
4
5

Sample Output

1
1
0
3
0

Source

2019 年百度之星·程序设计大赛 - 初赛一

解答

可以递推的计算，但是数据规模很大，复杂度过高，所以考虑可能会有规律。

可以先写一个程序输出前 50 项，观察一下。（python 实现）

a = 1
s = 0
i = 1
l = 0
print(i, '\t', a)
while i < 50:
    s += a * i 
    i += 1
    a = s % i
    print(i, '\t', a)

1      1
2      1
3      0
4      3
5      0
6      3
7      5
8      4
9      1
10     9
11     1
12     6
13     9
14     7
15     2
16     15
17     2
18     9
19     13
20     10
21     3
22     21
23     3
24     12
25     17
26     13
27     4
28     27
29     4
30     15
31     21
32     16
33     5
34     33
35     5
36     18
37     25
38     19
39     6
40     39
41     6
42     21
43     29
44     22
45     7
46     45
47     7
48     24
49     33
50     25

graph TD
    start(开始) --> input[输入 n]
    input --> is_even{是否是偶数}
    is_even --是--> mod6_4{模 6 余 4}
    mod6_4 --是--> output1[输出 n - 1]
    mod6_4 --否--> output2[输出 n / 2]
    is_even --否--> mod6_1{模 6 余 1}
    mod6_1 --是--> output3["输出 1 + 4 * ((n-1) / 6)"]
    mod6_1 --否--> output4["输出 ((n-1) / 6)"]

代码

#include <cstdio>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long n;
        scanf("%lld", &n);
        if (n == 1) {
            printf("1\n");
        }
        else {
            if (n % 2 == 0) {
                if (n % 6 == 4) {
                    printf("%lld\n", n - 1);
                }
                else {
                    printf("%lld\n", n >> 1);
                }
            }
            else {
                if ((n - 1) % 6 == 0) {
                    printf("%lld\n", 1 + 4 * ((n-1) / 6));
                }
                else {
                    printf("%lld\n", ((n-1) / 6));
                }
            }
        }
    }
}