hdu6222——佩尔方程&&大数__int128

题意

给定一个整数 $N$($1 \leq N \leq 10^{30}$)，求最小的整数 $t$，要求 $t \geq N$，使得边长为 $t-1, t, t+1$ 的三角形面积为整数。

分析

根据海伦公式：$S = \sqrt{p(p-a)(p-b)(p-c)}$，$p = \frac{a+b+c}{2}$.

代入，令 $\frac{t}{2}=x$，化简得 $S^2 = 3x^2(x^2-1)$.

题目要求 $S$ 为整数，则 $(x^2-1)$ 一定是3乘以一个平方数，

即 $x^2-1=3y^2$，即 $x^2-3y^2=1$.

易知最小解为(2, 1)，用递推式求出其他解即可。

由于题目 $N$ 的范围较大，到 1e30，可以使用 int128(1e38)，本地测试1e38内，只有67个解。

#include<bits/stdc++.h>

using namespace std;

const int maxn = +;

__int128 xx[maxn], yy[maxn];

void read(__int128 &x) {

    x = ;

    char ch;

    int flag = ;

    while (ch = getchar()) {

        if (ch == '-') flag = -;

        if (ch >= '' && ch <= '') break;

    }

    x = ch-'';

    while ((ch = getchar()) >= '' && ch <= '') {

        x = x* + ch-'';

    }

    x *= flag;

}

void out(__int128 x) {

    if (x < ) {

        x = -x;

        putchar('-');

    }

    if (x >= ) out(x / );

    putchar(x %  +'');

}

void init()

{

    xx[] = , yy[] = ;

    for(int i = ;i <= ;i++)

    {

        xx[i] = xx[i-]* + yy[i-]*;

        yy[i] = xx[i-] + yy[i-]*;

    }

}

int main()

{

    init();

    int T;

    scanf("%d", &T);

    while(T--)

    {

        __int128 n;

        read(n);

        for(int i = ;i <= ;i++)

        {

            if(xx[i]* >= n)

            {

                out(xx[i]*);

                printf("\n");

                break;

            }

        }

    }

}

顺便记个int128的模板，