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:

[ol]

• 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.

[/ol]

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

 

题意：给出n和k的值，问能否找到一个序列满足以下条件：1.这个序列长度为k，这k个数的和是n；2.这k个数中存在任意k-1个数的和是任意一个数的平方。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             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;}