HDU 4982 Goffi and Squary Partition（BestCoder Round #6）

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;

const int N=1e3+10;
const int M=50000;
const int INF=0x3f3f3f3f;

int main ()
{
    int n, k, sum, i, flag;
    int squre, remain;

    while (scanf("%d%d", &n, &k) != EOF)
    {
        flag = 0;
        sum = k*(k-1)/2; ///可以先令1~k-1这些数为前k-1个数（这是最小的k-1个数的和）

        for (i = 1; i*i < n; i++)
        {
            squre = i*i; ///完全平方数
            remain = n-squre; ///可能的第k个数

            if (sum > squre) continue; ///前k-1个数的和大于完全平方数，不符合题意
            if (remain <= k-1 && sum+k > n) continue; ///如果第k个数<=k-1，那么构造这个完全平方数时用到的最小的数是k，并且此时总和>n，不符合题意
            if (squre == sum+1 && remain == k) continue; ///如果完全平方数==sum+1，说明在构造完全平方数时需要用到k，而需要的第k个数也是k，产生矛盾

            flag = 1;
            break;
        }

        if (flag) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}