HDU 4982 Goffi and Squary Partition

Goffi and Squary Partition
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 856    Accepted Submission(s): 50
Problem Description
Recently, Goffi is interested in squary partition of integers.
A set
X of k distinct positive integers is called squary partition of n if and only if it satisfies the following conditions:

the sum of k positive integers is equal to n

one of the subsets of X containing k−1 numbers sums up to a square of integer.

For example, a set {1, 5, 6, 10} is a squary partition of 22 because 1 + 5 + 6 + 10 = 22 and 1 + 5 + 10 = 16 = 4 × 4.Goffi wants to know, for some integers n and k, whether there exists a squary partition of n to k distinct positive integers.
 
Input
Input contains multiple test cases (less than 10000). For each test case, there's one line containing two integers
n and k (2≤n≤200000,2≤k≤30).
 
Output
For each case, if there exists a squary partition of
n to k distinct positive integers, output "YES"in a line. Otherwise, output "NO".
 
Sample Input
2 2 4 2 22 4
 
Sample Output
NO YES YES
 

#include <vector> 

#include <list> 

#include <map> 

#include <set> 

#include <deque> 

#include <queue> 

#include <stack> 

#include <bitset> 

#include <algorithm> 

#include <functional> 

#include <numeric> 

#include <utility> 

#include <sstream> 

#include <iostream> 

#include <iomanip> 

#include <cstdio> 

#include <cmath> 

#include <cstdlib> 

#include <cctype> 

#include <string> 

#include <cstring> 

#include <ctime> 



using namespace std;



#define _int64 long long



int main()

{

  int n,k,tmp,sum,rem,b1,i;

  while (scanf("%d%d",&n,&k)!=EOF)

  {

    sum=(k*(k-1)/2);
　　//        1 k-1 
　　//    1 k-1  

    b1=0;
　　//flag

    for (i=1;i*i<n;i++)

    {

      rem=n-i*i;

      tmp=i*i;

      if (tmp<sum) continue;

      if ((rem<=k-1)&&(tmp-sum<k-rem)) continue;

      //if ((tmp==sum)&&(rem<=k-1)) continue;

      if ((tmp==sum+1)&&(rem==k)) continue;

      b1=1;

      //cout<<i<<endl;

      break;

    }

    if (b1==1) printf("YES
");

    else printf("NO
");

  }

  return 0;

}