HDU5312 Sequence-白红宇

HDU5312 Sequence

阅读量：6007 次

发布时间：2019-06-20

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

题意：t组数据，每组数据给个m。问m最少能由几项形如3*n*(n-1)+1的数表示

eg 7=1(n=1)+1(n=1)+1(n=1)+1(n=1)+1(n=1)+1(n=1)+1(n=1);

7=7(n=2);

所以7最少能由1个数表示

分析：3*n*(n-1)+1能够转换为6*(n*(n-1)/2)+1,而n*(n-1)/2是一个三角形数。设为An，

则m能够表示为m=6*(A1+A2+…+Ak)+k(如果m最少能由k个数表示)看，由三角形数的性质(一个自然数最多能由三个三角形数表示)可得,当k>=3时，A1+… +Ak能够表示随意自然数，此时k=(m-1)%6+1+6*n(n=0,1,2,…)（A1+A2+…Ak 是自然数）此时最小值k取n=0，即k=(m-1)%6+1(k>=3).另外，假设当n=0时， k的值为1或者2。此时须要考虑是否存在一个或者两个三角形数能表示出该数m。假设能够，则k的最小值即为1或者2。假设不能够，则取n=1， k+=6。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           using namespace std;const int maxn = 1e6+5;map
           
            Map;int v[maxn];int main(){ int t; for(int i=1;i<=100000;i++){ //预处理 int tmp=3*i*(i-1)+1; if(tmp>1e9) break; v[i]=tmp; Map[tmp]=1; //用于后面查看此数是否可以由3*n*(n-1)+1表示 } scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int k=(n-1)%6+1; //(n-1)%6+1==n%6=0?6:n%6,两种写法都可以 if(k>=3){ //k>=3,此时一定存在自然数能由A1+…Ak的数表示 printf("%d\n",k); } else if(k==1){ //k==1 检验n能否由该式子表示 if(Map.count(n)) printf("1\n"); else printf("7\n"); } else if(k==2){ //k==2，检验n能否由两个该式子的数表示 int flag=0; for(int i=1;v[i]<=n/2;i++){ if(Map.count(n-v[i])) flag=1; } if(flag) printf("2\n"); else printf("8\n"); } }}

转载地址：http://xasmx.baihongyu.com/

你可能感兴趣的文章