ZOJ - 3935 2016 【数的筛选】

题目链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3935

题意

要求找出 从 2016-990528 中 是闰年 并且满足

这两个公式的年份

输出就可以了

思路

其实可以发现 在第一个公式中 2016 = 63*64 第二个公式中 2016=32*63

然后 第一个公式 从 63开始跑 第二个公式从 32开始跑

用 MAP 保存 最后从小到大 输出 两个MAP中都有 并且是闰年的年份就可以

AC代码

#include <cstdio>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <climits>

#include <ctype.h>

#include <algorithm>

#include <deque>

#include <vector>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

 using namespace std;

 const int maxn = 990528;

 bool isleap(int x)

 {

     return ((x % 4 == 0 && x % 100 != 0) || (x % 400 == 0));

 }

int main()

{

    map <int, int> m[2];

    for (int i = 63; i * (i + 1) <= maxn * 2; i++)

        m[0][i * (i + 1) / 2] = 1;

    for (int i = 32; i * (2 * i - 1) <= maxn; i++)

        m[1][i * (2 * i - 1)] = 1;

    map <int, int>::iterator it;

    for (it = m[0].begin(); it != m[0].end(); it++)

    {

        if (m[1][it->first] && isleap(it->first))

            printf("%d\n", it -> first);

    }

}