HDU – 6222 Heron and His Triangle

• 2020 年 4 月 9 日
• 筆記

Link: Heron and His Triangle HDU – 6222

Heron and His Triangle

Description:

A triangle is a Heron』s triangle if it satisfies that the side lengths of it are consecutive integers t-1, t, t+ 1 and thatits area is an integer. Now, for given n you need to find a Heron』s triangle associated with the smallest t bigger

than or equal to n.

Input The input contains multiple test cases. The first line of a multiple input is an integer T (1 ≤ T ≤ 30000) followedby T lines. Each line contains an integer N (1 ≤ N ≤ 10^30).

Output For each test case, output the smallest t in a line. If the Heron』s triangle required does not exist, output -1.

Sample Input 4 1 2 3 4

Sample Output 4 4 4 4

Problem solving: 這道題的意思是給你一個n，讓你求一個大於n的最小的i，滿足邊為i，i+1，i-1的三角形的面積是整數。然後輸出 這道題的n範圍是10^30，肯定不能直接暴力寫。隊友用三角形的面積公式，打了個表，看了前滿足面積是整數的i的幾個數，對着那幾個數看了看，發現一個規律。ans[i]=4*ans[i-1]+ans[i-2]，也不知道對不對，就用python打了個表，把前10^30裏面滿足條件的值都寫了出來，因為不能用python交，所以那些數都用了字符串存了起來。最後輸入之後直接在字符串數組中找到第一個大於輸入的就行了。

Code:

#include<bits/stdc++.h>  using namespace std;  #define ll long long  #define fast ios::sync_with_stdio(false)    const int mod=1e9+7;  const int maxn=1e5+10;  string s[120]={"4","14","52","194","724","2702","10084","37634","140452","524174","1956244","7300802","27246964","101687054","379501252","1416317954","5285770564","19726764302","73621286644","274758382274","1025412242452","3826890587534","14282150107684","53301709843202","198924689265124","742397047217294","2770663499604052","10340256951198914","38590364305191604","144021200269567502","537494436773078404","2005956546822746114","7486331750517906052","27939370455248878094","104271150070477606324","389145229826661547202","1452309769236168582484","5420093847118012782734","20228065619235882548452","75492168629825517411074","281740608900066187095844","1051470266970439230972302","3924140458981690736793364","14645091568956323716201154","54656225816843604128011252","203979811698418092795843854","761263020976828767055364164","2841072272208896975425612802","10603026067858759134647087044","39571031999226139563162735374","147681101929045799118003854452","551153375716957056908852682434","2056932400938782428517406875284","7676576228038172657160774818702","28649372511213908200125692399524","106920913816817460143341994779394","399034282756055932373242286718052","1489216217207406269349627152092814","5557830586073569145025266321653204","20742106127086870310751438134520002","77410593922273912097980486216426804","288900269562008778081170506731187214","1078190484325761200226701540708322052","4023861667741036022825635656102100994","15017256186638382891075841083700081924","56045163078812495541477728678698226702","209163396128611599274835073631092824884","780608421435633901557862565845673072834","2913270289613924006956615189751599466452","10872472737020062126268598193160724792974","40576620658466324498117777582891299705444","151434009896845235866202512138404474028802","565159418928914618966692270970726596409764","2109203665818813240000566571744501911610254","7871655244346338341035574016007281050031252","29377417311566540124141729492284622288514754","109638014001919822155531343953131208104027764","409174638696112748497983646320240210127596302","1527060540782531171836403241327829632406357444","5699067524434011938847629318991078319497833474","21269209556953516583554114034636483645584976452","79377770703380054395368826819554856262842072334","296241873256566700997921193243582941405783312884","1105589722322886749596315946154776909360291179202","4126117016034980297387342591375524696035381403924","15398878341817034439953054419347321874781234436494","57469396351233157462424875086013762803089556342052","214478707063115595409746445924707729337576990931714","800445431901229224176560908612817154547218407384804","2987303020541801301296497188526560888851296638607502","11148766650265975981009427845493426400857968147045204","41607763580522102622741214193447144714580575949573314","155282287671822434509955428928295152457464335651248052","579521387106767635417080501519733465115276766655418894","2162803260755248107158366577150638708003642730970427524","8071691655914224793216385807082821366899294157226291202","30123963362901651065707176651180646759593533897934737284","112424161795692379469612320797639765671474841434512657934","419572683819867866812742106539378415926305831840115894452","1565866573483779087781356105359873898033748485925950919874","5843893610115248484312682314900117176208688111863687785044","21809707866977214849469373154240594806801003961528800220302"};    int main()  {      int n;string ss;      cin>>n;      while(n--)      {          cin>>ss;          for(int i=0;i<120;i++)          {              int x,y;              x=s[i].size(),y=ss.size();              if(x<y)    continue;              if(x==y)              {                  if(s[i]>=ss)                  {                      cout<<s[i]<<endl;                      break;                  }              }              if(x>y)              {                  cout<<s[i]<<endl;                  break;              }          }      }      return 0;  }

很長的一個表(2333