2014
02-10

# 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

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

(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;
}

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