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

赏