[2021.11.14]UPC-计算机2021随堂测验第四场-21232 Problem E 更多闰年数

本文主要是介绍[2021.11.14]UPC-计算机2021随堂测验第四场-21232 Problem E 更多闰年数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入2 个正整数a和b，表示开始的年份和结束的年份，问从a年到b年有多少闰年？

输入

第一行2个整数a和b（a≤b），范围在[1,  1,000,000,000]。

输出

只一个整数。

样例输入 Copy

1 10000

样例输出 Copy

2425

题解：

        类似的题做了n遍了，然而这次的数据量为10^9，于是...从a到b开始遍历逐年判断是否为闰年的时间复杂度为O(n)的常规方法被否决了  Sad  : (

        于是我们换个办法，可以每次加400年的方法来遍历，然而，代码实现有不少小困难需要解决。

以下是代码 : )

如有纰漏，还请多多指正！！！

该方法的时间复杂度大概仍为O(n),但对于10^9的数据量，执行的运算次数大约为10^9/400

为10^6~10^7 之间，1s还是绰绰有余的。 

#include <cstdio>
int main() {unsigned long long a,b,i,ans=0;scanf("%llu %llu",&a,&b);for(i=a;i<=b;i++){    //当i为400的整数倍时跳出，开始每次增加400年的遍历if(!(i%4)&&i%100)ans++;if(!(i%400)){ans++;break;}}i--;   //如果是因为不满足i<=b的条件而跳出，此时i为b+1if(i==b){    // 此时说明b-a<=400，不需要再进行遍历，直接输出。printf("%llu ",ans);return 0;}for(;i+400<b;i+=400){     //每400年 减去100 200 300 还有97个闰年。ans+=97;}for(i+=1;i<=b;i++){    //当i+400<b时 开始逐年遍历判断闰年。if(!(i%4)&&i%100)ans++;}printf("%llu",ans);return 0;
}

这篇关于[2021.11.14]UPC-计算机2021随堂测验第四场-21232 Problem E 更多闰年数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---