ACdream 그룹 트레이닝 경기(38)/J - Positive Negative Sign

J - Positive Negative Sign


Time Limit:
2000
MS     
Memory Limit:
32768
KB     
64bit IO Format:
unknown
Description
Given 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
-1 -2 -3 +4 +5 +6 -7 -8 -9 +10 +11 +12
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 ≤ 109, 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

12 3
4 1
Sample Output
Case 1: 18
Case 2: 2
분석:
간단한 문제.(자꾸 힘들게 끝내고 보니 간단한 문제였다...)
데이터 규모를 보면 왼쪽에서 오른쪽으로 계산하면 반드시 시간을 초과해야 한다는 것을 알 수 있다.(가소롭게도 한 번 더 해봤는데 그렇게 많은 시간을 낭비했어...)
이런 대규모 데이터는 단지 몇 가지 상황만 생각할 뿐이다. 2점?동규아니면 수학 공식?
분명히 이 문제는 수학 공식이다.우리는 n이 2m에서 제거될 수 있다는 것을 발견할 수 있다. 모든 수는 반드시 m개를 먼저 줄이고 m개를 더해야 한다.그러면 우리는 매번 1을 빼고 1을 더하면 마지막 결과는 m*m를 더 넣는다는 것을 한층 더 발견했다.예를 들어 -1,-2,-3,+4,+5,+6, (4-1)+(5-2)+(6-3)로 볼 수 있다.총 선감후 n/2m회 추가.그래서 마지막 결과는 m*m*n/2m=n*m/2입니다.
여기에 숫자의 범위를 관찰해야 한다. 최악의 경우 n=100000000m=500000000이기 때문에 마지막 답은 롱롱이 필요하다.
#include <iostream>

using namespace std;

int main()
{
    int t;
    long long n,m;
    cin>>t;
    for (int i=0;i<t;i++)
    {
        cin>>n>>m;
        long long ans=n*m/2;
        cout<<"Case "<<i+1<<": "<<ans<<endl;
    }


    return 0;
}

좋은 웹페이지 즐겨찾기