HDU 5312(数学推导+技巧)-白红宇

HDU 5312(数学推导+技巧)

阅读量：6006 次

发布时间：2019-06-20

本文共 1341 字，大约阅读时间需要 4 分钟。

首先说一下。N*（N-1）/2为三角形数，随意一个自然数都最多可由三个三角形数表示。

对于，对于给定的要求值 V, 那么其一组解可表示为 V = 6*（K个三角形数的和）+K；即随意由k个数组成的解都有（V-K）%6==0;

那么仅仅须要找到最小的K（1,2须要特判，结论最小值为3）；

在对2进行特判时候，能够从两端到中间的线性扫描来做。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         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;}