lightoj1294

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1294 - Positive Negative Sign

-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12Given two integers: n and m and n is divisible by 2m, you have to write down the first n natural numbers in the following form. At first take first m integers and make their sign negative, then take next m integers and make their sign positive, the next m integers should have negative signs and continue this procedure until all the n integers have been assigned a sign. For example, let n be 12 and m be 3. Then we have

If n = 4 and m = 1, then we have

-1 +2 -3 +4

Now your task is to find the summation of the numbers considering their signs.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing two integers: n and m (2 ≤ n ≤ 10⁹, 1 ≤ m). And you can assume that n is divisible by 2*m.

Output

For each case, print the case number and the summation.

Sample Input	Output for Sample Input
212 34 1	Case 1: 18Case 2: 2

题目类型：数学题

算法分析：直接模拟计算会TLE，这里应该将负数项和正数项分开，发现每一个序列都构成一个等差序列，然后直接使用公式计算出两个序列的和，最后两个序列和再相减即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 66 + 66;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        long long n, m;
        cin >> n >> m;

        long long a1 = (1 + m) * m / 2, b1 = ((1 + m) + (1 + m + m - 1)) * m / 2;
        long long len = n / (2 * m);

        long long an = a1 + (len - 1) * (2 * m), bn = b1 + (len - 1) * (2 * m);
        long long suma = (a1 + an) * len / 2, sumb = (b1 + bn) * len / 2;

        cout << sumb - suma << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 66 + 66;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

long long n, m;

cin >> n >> m;

long long a1 = (1 + m) * m / 2, b1 = ((1 + m) + (1 + m + m - 1)) * m / 2;

long long len = n / (2 * m);

long long an = a1 + (len - 1) * (2 * m), bn = b1 + (len - 1) * (2 * m);

long long suma = (a1 + an) * len / 2, sumb = (b1 + bn) * len / 2;

cout << sumb - suma << endl;

}

return 0;

}

lightoj1266

lightoj1319

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1294

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论