Goffi and Squary Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1588 Accepted Submission(s): 527
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。问是否存在一个k个数字的序列，和为n，并且其中存在k-1个数字的和是一个完全平方数。
例如：{1, 5, 6, 10}, n为22，k为 3的时候， 1 + 5 + 6 + 10 = 22 and 1 + 5 + 10 = 16 = 4 × 4.所以符合
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
int main()
{
int n, k;
while (scanf("%d%d", &n, &k) != EOF)
{
int flag = 0;
int sum = k * (k - 1) / 2;
for (int i = 1; i * i < n; i++)
{
int squre = i * i;
int need = n - squre;
if (squre < sum)
{
continue;
}
if (need <= k - 1 && sum + k > n)
{
continue;
}
if (squre == sum + 1 && need == k)
{
continue;
}
flag = 1;
break;
}
if (flag)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
