第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）G Fibonacci

标签：奇偶 竞赛 奇数 45 long ICPC 偶数 Fibonacci

牛客竞赛传送门：

　　本题链接：G-Fibonacci_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）(重现赛) (nowcoder.com)

　　比赛完整题单：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

通过率：702/961

题目大意：给定一个整数 n ,计算有多少对 (x,y) 满足 1≤x<y≤n，且fx​∗fy​ 的值为偶数

　　　　【说明】在样例1中，满足条件的数对有（1，3），（2，3），对应f1​∗f3​=1∗2=2，f2​∗f3​=1∗2=2

知识点：组合数学、数学推理

思路： 　　因为最后只需要找fx∗fy的值为偶数 　　所以，其实斐波那契只是外表的包装，我们只需要找到奇偶规律就行 　　1,1,2,3,5,8,13,21,34 　　1,1,0,1,1,0, 1, 1, 0(1表示奇数，0表示偶数) 　　不难发现，奇偶规律：周期为3的奇数奇数偶数 　　0*0=0，1*0=0，1*1=1 　　所以用所有的组合数 减去 所有奇数的组合数，就是答案 　　本题数字较大，注意要开long long AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long c(long long x){
 5     return x*(x-1)/2;
 6 }
 7 
 8 int main(){
 9     long long n ; cin>>n;
10     printf("%lld", c(n) - c(n-n/3));
11     return 0;
12 }
13 
14 /*
15 知识点：组合数学、数学推理
16 
17 思路：
18 因为最后只需要找fx∗fy的值为偶数
19 所以，其实斐波那契只是外表的包装，我们只需要找到奇偶规律就行
20 1,1,2,3,5,8,13,21,34
21 1,1,0,1,1,0, 1, 1, 0(1表示奇数，0表示偶数)
22 不难发现，奇偶规律：周期为3的奇数奇数偶数
23 0*0=0，1*0=0，1*1=1
24 所以用所有的组合数 减去 所有奇数的组合数，就是答案
25 本题数字较大，注意要开long long
26 
27 耗时：15min
28 */

 

标签：奇偶,竞赛,奇数,45,long,ICPC,偶数,Fibonacci
From： https://www.cnblogs.com/--OvO--/p/16838614.html