Goffi and Squary Partition

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1171    Accepted Submission(s): 402

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

 

 

Source

 

构造数组出来，真的难想到，无比佩服能够想到的大牛。。分析都在代码里。。

/**题意:给你k个数(各不相同的正整数),它们的和是n，问是否存在k-1个数的和是某个数的平方?分析:我们假设其中k-1个数个数的平方为 m , m 应该不小于 k*(k-1)/2,不然就会有重复的 。我们可以通过构造一个序列来判断是否满足条件。*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long LL;int n,k;bool judge(int m){ int t = n-m, sum = (k-1)*k/2; if(sum>m) return false; ///k-1项最小都要 sum int count=0,x=0; for(int i=1;i