Problem Description
Today, Soda has learned a sequence whose n-th (n≥) item is 3n(n−)+. Now he wants to know if an integer m can be represented as the sum of some items of that sequence. If possible, what are the minimum items needed? For example, =+++=+++.
Input
There are multiple test cases. The first line of input contains an integer T (≤T≤), indicating the number of test cases. For each test case: There's a line containing an integer m (1≤m≤109).
Output
For each test case, output − if m cannot be represented as the sum of some items of that sequence, otherwise output the minimum items needed.
Sample Input
Sample Output
Source
对于这种题，首先一开始就要对给出的公式进行研究，从这里入手是正道。
分析公式 3n(n−1)+1 ，若给出一个数n，假设要k个3n(n−1)+1加起来得到n，即 3n(n-1)k+k=n,注意到3n(n-1)k是6的倍数，那么求的是满足（n-k）%6==0的最小的k。还有就是要注意到1、2要特判，即k要从3开始枚举
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<stdlib.h>
#include<map>
using namespace std;
#define N 20000
int num[N];
int n;
void init(){
for(int i=;i<N;i++){
num[i]=*i*(i-)+;
}
}
bool check1(){
for(int i=;i<N;i++){
if(num[i]==n)
return true;
}
return false;
}
bool check2(){
int j=N-;
for(int i=;i<N;i++){
while(num[i]+num[j]>n && j>) j--;
if(num[i]+num[j]==n && j>){
return true;
}
}
return false;
}
int main()
{
init();
int t;
scanf("%d",&t);
while(t--){ scanf("%d",&n);
if(check1()){
printf("1\n");
}
else if(check2()){
printf("2\n");
}
else{
for(int i=;i<;i++){
if((n-i)%==){
printf("%d\n",i);
break;
}
}
}
}
return ;
}