1327-A, *1100

Problem - 1327A - Codeforces

문제

• $t(1 \leq t \leq 10^{5})$번의 test case 로 구성되어 있다
• $n(1 \leq n \leq 10 ^{7})$이 서로다른 $k(1 \leq k \leq 10^{7})$개의 홀수 자연수의 합이 될 수 있나? ~ !
• ! 가 $O(log\ n)$ 정도의 알고리즘이면 통과할 수 있다

 

$O(t)$

$k$가 주어졌을 때 ! 가 가능한 $n$들의 집합을 구하자

서로 다른 $k$개의 홀수 자연수 합의 최소값은
$$\sum_{i=1}^{k}(2i-1) = k^{2} \Rightarrow n \geq k^{2}$$

또한,
$$\mathrm{Sum\ of\ k\ odd\ number} = \left.
  \begin{cases}
    \mathrm{odd}, & \mathrm{k\ is\ odd} \\
    \mathrm{even}, & \mathrm{k\ is\ even}
  \end{cases}
  \right\}$$

따라서 ! 가 가능한 $n$ 집합은 집합 $S$의 부분집합이다
$$S=\left \{ n |\ n \geq k^{2}\ \mathrm{and}\ k \equiv n (mod\ 2) \right \}$$

 

Claim
! 가 가능한 $n$ 집합은 $S$와 같다

$\because$ 서로 다른 $k$개의 홀수 자연수 합이 최솟값인 경우를 보자
$${1, 3, 5, 7, ... , 2k-1}$$
이때 $2k-1$을 2씩 증가시켜도, 서로다른 홀수 자연수 집합이다

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    ll n, k;
    while(t--){
        cin >> n >> k;
        cout << ((n >= k*k && ((k%2) == (n%2)))? "YES": "NO") << endl;
    }
 
 
    return 0;
}cs