1.一道数论题(用数学知识优化)

3的倍数

时间限制 7ms

内存限制 1.00MB

题目背景

传奇的一中数学班出了一道题目...

题面翻译

Can you speak Chinese?

题目描述

给定n个不超过10000的正整数 然后将它们按顺序排成一列({2,4,6,8} = 2468) 输出这个数mod 3的结果

输入格式

第一行 输入一个正整数n$(50 ≤ n ≤ 5000)$

第二行 输入n个正整数$a_i(1 ≤ a_i ≤ 10000)$ 每个数之间用一个空格隔开

输出格式

一个正整数 表示组合后的数mod 3的结果

样例 #1

样例输入 #1

50
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

样例输出 #1

0

提示

样例说明: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950是3的倍数 不信自己算

提示: 尽你所能地优化

--------------------------------------------分割线--------------------------------------------

--------------------------------------------分割线--------------------------------------------

2.算法题(具体什么算法我就不说了)

小徐爱函数

时间限制 10ms

内存限制 512.00MB

题目背景

优化代码 从你我做起

题目描述

有一天，小徐在上数学课，他突发奇想，写出了以下函数:

$$f(x)=f(\lfloor x\div 2\rfloor) + f(x-2)\\ f(0)=1\ \ \ \ \ \ \ f(1)=2 $$

小徐写出函数后 决定求出f(2)至f(n)的值 但是由于小徐智力低下 做不到这一点 请你写一个程序 帮他计算f(2)至f(n)的值

输入格式

第一行 一个整数n$(2≤n≤10000)$

输出格式

共$n-1$行 第$i$行为$f(i+1)$的值

样例 #1

样例输入 #1

20

样例输出 #1

3
4
6
7
10
11
16
17
23
24
33
34
44
45
60
61
77
78
100

提示

提示1:十年OI一场空 不开long long见祖宗

提示2:单纯的递归是不是会TLE呢