第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(上海)G 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代码:
#include<bits/stdc++.h>
using namespace std;
long long c(long long x){
return x*(x-1)/2;
}
int main(){
long long n ; cin>>n;
printf("%lld", c(n) - c(n-n/3));
return 0;
}
/*
耗时:15min
*/