首页 > ACM题库 > HDU-杭电 > HDU 2802-HOJ-F(N)-数论-[解题报告]C++
2014
02-17

HDU 2802-HOJ-F(N)-数论-[解题报告]C++

F(N)

问题描述 :


Giving the N, can you tell me the answer of F(N)?

输入:

Each test case contains a single integer N(1<=N<=10^9). The input is terminated by a set starting with N = 0. This set should not be processed.

输出:

Each test case contains a single integer N(1<=N<=10^9). The input is terminated by a set starting with N = 0. This set should not be processed.

样例输入:

1
2
3
0

样例输出:

1
7
20

刚做完一道推公式题,这题跟上一题解题思路很像。做完后上网搜索,发现有些人不是我这样做的,他们是发现了结果中有循环节,不过我还是觉得我的做法更巧妙。

我的做法如下:

首先推出公式f(n)=cell[(n+1)*(n+1)*(2n-1)/4];

这里涉及浮点数向上取整问题,将会给取余操作带来很大的麻烦,于是分类讨论之,我们记g(n)=(n+1)*(n+1)*(2n-1)。

显然,当n为奇数时,g(n)能被4整除

当n为偶数时,我们将g(n)等价转换为:n*n*(2n-1)+4*n*n-1,于是结论就显然了,g(n)+1一定能被4整除,这正是结果向上取整后的结果。

接下来就用我上一题的方法如法炮制就行了。

/*
 * hdu2802/win.cpp
 * Created on: 2011-10-28
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MOD = 2009 * 4;

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int n;
    long long ans;
    while (scanf("%d", &n) == 1 && n > 0) {
        ans = (n + 1);
        ans *= (n + 1);
        ans %= MOD;
        ans *= (2 * n - 1);
        ans %= MOD;
        if (n % 2 == 0) {
            ans++;
        }
        ans %= MOD;
        ans /= 4;
        printf("%d\n", (int) ans);
    }
    return 0;
}

解题参考:http://www.cnblogs.com/moonbay/archive/2011/10/28/2228163.html


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”