#include<iostream>
#include<cmath>
using namespace std;
int compare(const void* a,const void* b) {
int* tempa = (int*)a;
int* tempb = (int*)b;
return *tempa - *tempb ;
}
void is(int parr[], int pidx, int fidx, int key,bool *pbool) {
if (key == 0) {
*pbool = true;
}
else if (key < 0)return;
else if (fidx > pidx) {
return;
}
else {
is(parr, pidx, fidx + 1, key, pbool);
is(parr, pidx, fidx + 1, key - parr[fidx], pbool);
}
}
int main() {
int k;
cin >> k;
while (k--) {
int n;
bool greater = false;
int temp=0;
cin >> n;
double sqr = sqrt(n);
int *arr = new int[((int)sqr * 2)+1];
int arrtemp = 0;
int sum = 1;
arr[arrtemp++] = 1;
if (((int)sqr*(int)sqr) == n) {
sum += sqr;
}
for (int i = 2;i < sqr;i++) {
if (n%i == 0) {
arr[arrtemp++] = i;
arr[arrtemp++] = (n / i);
sum += i;
sum += (n / i);
}
}
if (sum >= n) {
greater = true;
}
if (!greater)
cout << "not weild" << endl;
else
{
qsort(arr, arrtemp, sizeof(int),compare);
if ((sum - n) > n) {
temp = n;
}
else {
temp = sum - n;
}
int idx=0;
for (idx;arr[idx] < temp&&idx <= arrtemp;idx++);
bool check = false;
is(arr, idx, 0, temp,&check);
if (check)
cout << "not weild" << endl;
else
cout << "weild" << endl;
}
}
return 0;
}
is함수가 sum이 n보다 큰경우에는 그 차 혹은 n을 key값으로 이용해서 key값보다 작은 약수들을 인덱스 0부터 시작해서 빼거나 빼지 않으면서 모든 부분집합의 차를 구하는 함수인데요 이게 아무래도 지수승의 시간복잡도를 가지니까 느린거같기도 한데 ㅠ 이런식으로 접근하면 안되는 건가요??
개잉룡
is함수가 sum이 n보다 큰경우에는 그 차 혹은 n을 key값으로 이용해서 key값보다 작은 약수들을 인덱스 0부터 시작해서 빼거나 빼지 않으면서 모든 부분집합의 차를 구하는 함수인데요 이게 아무래도 지수승의 시간복잡도를 가지니까 느린거같기도 한데 ㅠ 이런식으로 접근하면 안되는 건가요??
10년 전