[HDU6222]Heron and His Triangle

2024-03-16 23:32

文章标签 triangle heron hdu6222

本文主要是介绍[HDU6222]Heron and His Triangle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Heron and His Triangle

题解

~~很水的一道找规律题呀~~

~~由T**M*E***的要求，还是写一下Pell方程的做法吧~~

由海伦公式可知， $S= \sqrt{p(p-a)(p-b)(p-c)}$

$\because a=t-1,b= t,c=t+ 1$ ， $\therefore p=\frac{a+b+c}{2}= \frac{3t}{2}$

$\therefore S= \sqrt{ \frac{3}{2} t \cdot (\frac{1}{2} t+ 1) \cdot \frac{1}{2} t \cdot (\frac{1}{2} t-1) }$

令 $x=\frac{t}{2}$ ，则 $S=\sqrt{3x^2(x^2-1)}$

$\therefore 3x^2(x^2-1)= S^2$

由于 $S\in Z^{+}$ ，所以 $x^2-1$ 肯定是平方数。

所以 $x^2-3y^2= 1$ 。

所以我们可以得到递推公式，即每个区间的取值公式：

$a_{i}=4a_{i-1}-a_{i-2}$ ，找到比n大的最小的一个 $a_{i}$ ，输出即可。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
using namespace std;
typedef __int128 _LL;
typedef long long LL;
typedef pair<int,int> pii;
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void write(_T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
struct bigInt{int a[505],len;bigInt(){memset(a,0,sizeof(a));len=0;}bigInt(int num){*this=bigInt();while(num) a[++len]=num%10,num/=10;}int& operator [] (int index){return a[index];}void getIn(){char s[505];scanf("%s",s+1);len=strlen(s+1);for(int i=1;i<=len;i++)a[len-i+1]=s[i]-'0';}void rev(){for(int i=1;i*2<=len;i++)swap(a[i],a[len-i+1]);}bigInt operator / (const int num){bigInt res=*this;int x=0;for(int i=len;i>0;i--)res[i]=(x*10+a[i])/num,x=(x*10+a[i])%num;res.len=len;while(res.len>1&&!res[res.len]) res.len--;return res;}int operator % (const int num){int x=0;for(int i=len;i>0;i--)x=(a[i]+x*10)%num;return x;}bool zero()const{return len==1&&!a[1];}void print()const{for(int i=len;i>0;i--)write(a[i]);puts("");}bigInt operator + (bigInt other){bigInt res=bigInt(0);int x=0;res.len=1;for(int i=1;i<=len||i<=other.len;i++,res.len++){res[i]=(a[i]+other[i]+x)%10;x=(a[i]+other[i]+x)/10;}res[res.len]=x;while(res.len>1&&!res[res.len]) res.len--;return res;}bigInt operator * (bigInt other){bigInt res=bigInt(0);for(int i=1;i<=len;i++){int x=0;for(int j=1;j<=other.len;j++){x=res[i+j-1]+a[i]*other[j]+x;res[i+j-1]=x%10;x/=10;}res[i+other.len]=x;}res.len=other.len+len;while(res.len>1&&!res[res.len])res.len--;return res;}bigInt operator * (const int num){return *this*bigInt(num);}bigInt operator - (bigInt other){bigInt res=*this;for(int i=1;i<=len;i++){if(res[i]<other[i])res[i+1]--,res[i]+=10;res[i]-=other[i];}while(res.len>1&&!res[res.len]) res.len--;return res;}bool operator < (bigInt &other)const{if(len<other.len)return true;if(len>other.len)return false;for(int i=len;i;i--){if(a[i]<other[i])return true;if(a[i]>other[i])return false;}return false;}bool operator > (bigInt &other)const{if(len>other.len)return true;if(len<other.len)return false;for(int i=len;i;i--){if(a[i]>other[i])return true;if(a[i]<other[i])return false;}return false;}bool operator == (bigInt &other)const{if(len<other.len)return false;if(len>other.len)return false;for(int i=len;i;i--){if(a[i]<other[i])return false;if(a[i]>other[i])return false;}return true;}bool judge(){return len>=32;}
}num[500],n,m1,m2,m3,m4;//以前做玛琪露数时的模板，改改就拿来用了
int compare(bigInt x,bigInt y){if(x==y)return 2;if(x>y)return 1;if(x<y)return 0;
}
int t;
signed main(){num[0]=bigInt(4);num[1]=bigInt(14);for(int i=2;i;i++){num[i]=num[i-1]*4-num[i-2];if(num[i].judge())break;}read(t);m1=bigInt(1);m2=bigInt(2);m3=bigInt(3);m4=bigInt(4);while(t--){n.getIn();int fg=0,cnt;if(n==m1||n==m2||n==m3||n==m4){puts("4");continue;}for(int i=0;;i++){int x=compare(n,num[i]);if(fg==1&&x!=1){cnt=i;break;}if(x==1)fg=1;}num[cnt].print();}return 0;
}