首先说一下。N*（N-1）/2为三角形数，随意一个自然数都最多可由三个三角形数表示。
对于，对于给定的要求值 V, 那么其一组解可表示为 V = 6*（K个三角形数的和）+K； 即随意由k个数组成的解 都有 （V-K）%6==0;
那么仅仅须要找到最小的K（1,2须要特判，结论最小值为3）；
在对2进行特判时候，能够从两端到中间的线性扫描来做。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
typedef long long LL;
const int N = 100005; int n,f[N];
void init(){
for(int i=1;;i++){
int num= 3*i*(i-1)+1;
f[i]=num;
if(num>1e9){
n=i;
break;
}
}
}
int get(int v){
int p = lower_bound(f+1,f+1+n,v)-f;
return f[p]==v;
}
int find_(int v){
int l=1,r=n;
while(l<=r){
if(f[l] + f[r] < v) return 0;
while(l<=r){
if(f[l]+f[r] < v) {r++; break;}
else if(f[l]+f[r]==v) return 1;
else r--;
}
l++;
}
return 0;
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--){
int k; scanf("%d",&k);
if(get(k)) printf("1\n");
else{
int ok=0;
if((k-2)%6 == 0){
if(find_(k)) {ok=1;}
}
if(ok) printf("2\n");
else {
for(int i=3;i<=8;i++){
if((k-i)%6 == 0){
printf("%d\n",i);
break;
}
}
}
}
}
return 0;
}