首页 > ACM题库 > HDU-杭电 > hdu 2576 Another Sum Problem-数论-[解题报告]C++
2014
02-10

hdu 2576 Another Sum Problem-数论-[解题报告]C++

Another Sum Problem

问题描述 :

FunnyAC likes mathematics very much. He thinks mathematics is very funny and beautiful.When he solved a math problem he would be very happy just like getting accepted in ACM.Recently, he find a very strange problem.Everyone know that the sum of sequence from 1 to n is n*(n + 1)/2. But now if we create a sequence which consists of the sum of sequence from 1 to n. The new sequence is 1, 1+ 2, 1+2+3, …. 1+2+…+n. Now the problem is that what is the sum of the sequence from1 to 1+2+…+n .Is it very simple? I think you can solve it. Good luck!

输入:

The first line contain an integer T .Then T cases followed. Each case contain an integer n (1 <= n <= 10000000).

输出:

The first line contain an integer T .Then T cases followed. Each case contain an integer n (1 <= n <= 10000000).

样例输入:

3
1
24
56

样例输出:

1
2600
30856

题目蛮简单的,但是纠结了好久。原因倒不是推不出公式,而是推出公式以后不好办,因为公式是(n+2)*(n+1)*n/6,而n最大为10000000,这样的话即使用long long 也存不下。记得同余公式里关于除法的好像只有逆元的一些,上网找了一下,确定没有。于是只有自己继续推了。最后,自己终于证明了如下公式:

不妨设a > b,r为a、b的公约数,则有

(a/r)%(b/r) = (a%b)/r。

不知道这个公式之前有没有人推出来过,反正自己挺有成就感的。其实也很好证明,如下:

设(a/r)%(b/r) = z,则一定有且仅有一个k满足(a/r) = k(b/r) + z。

从而得a = kb + zr

于是有a%b=(kb+zr)%b=((kb)%b+zr%b)%b=(zr%b)%b

由上述假设易知z <(b/r),从而得zr<b

故(zr%b)%b = zr

故a%b=zr

从而

(a%b)/r = z = (a/r)%(b/r)

证毕。

有了公式,这题就是水题了。

/*
 * hdu2576/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 = 20090524 * 6;

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

解题转自:http://www.cnblogs.com/moonbay/archive/2011/10/28/2228125.html


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。