2019年浙江省赛 I Fibonacci in the Pocket

2019/05/04 10:23
阅读数 53

链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4108

题意:求第l个斐波那契数到第r个斐波那契数的和,判断这个和奇偶性,若为奇输出1,偶输出0

题解:很明显要利用前缀和,通过打表可以发现斐波那契前缀和的奇偶性为 奇 偶 偶 ,循环节长度为3,f(i)表示第i个前缀和,l到r的斐波那契数求和等于f(l)-f(r-1),所以只需要判断l和r-1对三取余的结果就可以判断f(l)和f(r-1)的奇偶性。注意到题目给的数据范围特别大,所以需要用大数模拟取余,我不会嫌麻烦就直接用python写了

代码:

 1 n = int(input())
 2 while n:
 3     n = n - 1
 4     a,b = map(int,raw_input().split())
 5     if a == 1:
 6         b = b % 3
 7         print(b % 2)
 8     else:
 9         b = b % 3
10         a = (a - 1) % 3
11         a = a % 2
12         b = b % 2
13         if a == b:
14             print(0)
15         else:
16             print(1)

备注:要特判r=1的情况

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部