题面（本人翻译）

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.

一个三角形是 Heron 三角形仅当它的三边长是连续的正整数 t - 1, t, t + 1，并且面积是正整数。现在，给你一个整数 N ，求大于等于 N 的最小的合法的 t （Heron 三角形的第二小的边）。

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).

一个正整数 T 表示数据组数，1 ≤ T ≤ 30000。接下来 T 行每行一个整数 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.

每个数据输出一行，即题意中的最小的 t ，如果没有满足要求的 Heron 三角形，输出 -1。

Sample Input

Sample Output

题解

我们可以用海伦公式表示面积

$\begin{align*} S &= \sqrt{\frac{3}{2}t(\frac{3}{2}t-t)(\frac{3}{2}t-t-1)(\frac{3}{2}t-t+1)}\\ &= \sqrt{\frac{3}{4}t^2(\frac{t^2}{4}-1)}\\ &= t\sqrt{\frac{3}{4}(\frac{t^2}{4}-1)}\\ &= t\sqrt{\frac{3t^2}{16}-\frac{3}{4}} \end{align*}$

我们设 x = t/2，y = 2S/t，那么

$\begin{align*} &\frac{3}{4}x^2-\frac{3}{4} = \frac{y^2}{4}\\ &\frac{3}{4}\cdot x^2 - \frac{3}{4} \cdot \frac{1}{3}\cdot y^2 = \frac{3}{4}\\ &x^2-\frac{1}{3} y^2 = 1 \end{align*}$

这是pell方程的形式，所以先手算出最小的解 x=2，y=3，然后我们用pell方程的递推式：

$\begin{align*} X_n &= X_{n-1}X_1+dY_{n-1}Y_1\\ Y_n &= X_{n-1}Y_1+Y_{n-1}X_1 \end{align*}$

我们会发现X增长得很快，到第52个就超过十的三十次方了，因此我们可以先打个表

X[1] = 4;

X[2] = 14;

X[3] = 52;

X[4] = 194;

X[5] = 724;

X[6] = 2702;

X[7] = 10084;

X[8] = 37634;

X[9] = 140452;

X[10] = 524174;

X[11] = 1956244;

X[12] = 7300802;

X[13] = 27246964;

X[14] = 101687054;

X[15] = 379501252;

X[16] = 1416317954;

X[17] = 5285770564;

X[18] = 19726764302;

X[19] = 73621286644;

X[20] = 274758382274;

X[21] = 1025412242452;

X[22] = 3826890587534;

X[23] = 14282150107684;

X[24] = 53301709843202;

X[25] = 198924689265124;

X[26] = 742397047217294;

X[27] = 2770663499604052;

X[28] = 10340256951198914;

X[29] = 38590364305191604;

X[30] = 144021200269567502;

X[31] = 537494436773078404;

X[32] = 2005956546822746114;

X[33] = 7486331750517906052;

X[34] = 27939370455248878094;

X[35] = 104271150070477606324;

X[36] = 389145229826661547202;

X[37] = 1452309769236168582484;

X[38] = 5420093847118012782734;

X[39] = 20228065619235882548452;

X[40] = 75492168629825517411074;

X[41] = 281740608900066187095844;

X[42] = 1051470266970439230972302;

X[43] = 3924140458981690736793364;

X[44] = 14645091568956323716201154;

X[45] = 54656225816843604128011252;

X[46] = 203979811698418092795843854;

X[47] = 761263020976828767055364164;

X[48] = 2841072272208896975425612802;

X[49] = 10603026067858759134647087044;

X[50] = 39571031999226139563162735374;

X[51] = 147681101929045799118003854452;

X[52] = 551153375716957056908852682434;

X[53] = 2056932400938782428517406875284; // 此处就超过 10^30 了

然后就二分判断就过了。

这题根本就不存在 -1。

ＣＯＤＥ

zxy tql %%%%%%

#include<cstdio>

#include<cstring>

#include<vector>

#include<stack>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#include<bitset>

#include<ctime>

#include<iostream>

#define MAXN 2005

#define LL long long

#define ULL unsigned LL

#define rg register

#define lowbit(x) (-(x) & (x))

#define ENDL putchar('\n')

#define DB double

//#define bs bitset<1005>

//#pragma GCC optimize(2)

//#pragma G++ optimize(3)

//#define int LL

using namespace std;

char char_read_before = 1;

inline int read() {

	int f = 1,x = 0;char s = char_read_before;

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x = x * 10 - '0' + s;s = getchar();}

	char_read_before = s; return x * f;

}

inline char readchar() {

	char s = char_read_before;

	while(s == 1 || s == ' ' || s == '\n') s = getchar();

	char_read_before = 1; return s;

}

LL zxy = 100000000;

int n,m,i,j,s,o,k;

DB bg;inline DB Time() {return DB(clock() - bg) / CLOCKS_PER_SEC;}

struct Num{

	LL s[4];

	Num(){s[0]=s[1]=s[2]=s[3]=0;}

	Num(int b) {s[0] = b;s[1] = s[2] = s[3] = 0;}

	Num operator = (int b) {

		s[0] = b;

		s[1] = s[2] = s[3] = 0;

		return *this;

	}

	void tl() {

		s[0] *= 10;

		s[1] = s[1] * 10 + s[0] / zxy;

		s[2] = s[2] * 10 + s[1] / zxy;

		s[3] = s[3] * 10 + s[2] / zxy;

		s[0] %= zxy;

		s[1] %= zxy;

		s[2] %= zxy;

	}

};

inline Num operator *(Num a,Num b) {

	Num c;

	for(int i = 0;i < 4;i ++) {

		LL m = 0;

		for(int j = 0;i+j < 4;j ++) {

			c.s[i+j] += a.s[i] *1ll* b.s[j] + m;

			m = c.s[i+j] / zxy;

			c.s[i+j] %= zxy;

		}

	}return c;

}

inline Num operator +(Num a,Num b) {

	LL m = 0;

	for(int i=0;i<4;i++) {

		a.s[i] += b.s[i] + m;

		m = a.s[i] / zxy;

		a.s[i] %= zxy;

	}return a;

}

inline bool operator < (Num a,Num b) {

	if(a.s[3] != b.s[3]) return a.s[3] < b.s[3];

	if(a.s[2] != b.s[2]) return a.s[2] < b.s[2];

	if(a.s[1] != b.s[1]) return a.s[1] < b.s[1];

	return a.s[0] < b.s[0];

}

inline bool operator >= (Num a,Num b) {return !(a < b);}

inline void print(Num a) {

	int le = 0;

	if(a.s[3]) le = 3;

	else if(a.s[2]) le = 2;

	else if(a.s[1]) le = 1;

	printf("%d",a.s[le]);

	while(le --) printf("%08d",a.s[le]);

	return ;

}

inline Num readn() {

	int f = 1;Num x(0);char s = char_read_before;

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x.tl();x = x + Num(s - '0');s = getchar();}

	char_read_before = s; return x;

}

struct mat{

	int n,m;

	Num s[3][3];

	mat(){n=m=0;s[1][1]=s[1][2]=s[2][1]=s[2][2]=Num();}

}A,B;

inline mat operator * (mat a,mat b) {

	mat c; c.n = a.n;c.m = b.m;

	for(int i=1;i<=c.n;i++)

		for(int k=1;k<=a.m;k++)

			for(int j=1;j<=c.m;j++)

				c.s[i][j] = c.s[i][j] + a.s[i][k] * b.s[k][j];

	return c;

}

Num as[100];

signed main() {

	bg = clock();

	A.n = 1;

	A.m = B.n = B.m = 2;

	A.s[1][1] = 2;

	A.s[1][2] = 3;

	B.s[1][1] = 2;

	B.s[2][1] = 1;

	B.s[1][2] = 3;

	B.s[2][2] = 2;

	for(int i = 0;i <= 52;i ++) {

		as[i] = A.s[1][1] * Num(2);

		A = A * B;

	}

	int T = read();

	while(T --) {

		Num nn = readn();

		int l = 0,r = 52,mid;

		while(l < r) {

			mid = l + r >> 1;

			if(as[mid] >= nn) r = mid;

			else l = mid+1;

		}

		print(as[l]);

		ENDL;

	}

	return 0;

}

巴特西

HDU 6222 Heron and His Triangle (pell 方程)