HDU 2281 Square Number: Pell方程及数论

HDU 2281 Square Number: Pell方程及数论2014-07-08 synapse7 http://acm.hdu.edu.cn/showproblem.php？pid=2281

思路：

原式化为：m^2-48x^2=1，（m=4n+3）

立即得到最小正整数解：m1=7，x1=1

后面就和uva 138一样了。

注意：得到mk后还要判断（mk-3）%4==0才能加到n中，详见代码。完整代码：

01./*31ms,276KB*/02.03.#include<cstdio>04.#include<vector>05.using namespace std;06.typedef __int64 ll;07.const ll maxn = 1e18;08.09.ll n[20], x[20];10.vector<ll> nn, xx;11.12.int main（）13.{14.int i;15.long long N;16.n[0] = 7LL, x[0] = 1LL;17.nn.push_back（1LL）, xx.push_back（1LL）;18.for （i = 1;; ++i）19.{20.n[i] = 7LL * n[i - 1] + 48LL * x[i - 1];21.x[i] = n[i - 1] + 7LL * x[i - 1];22.if （n[i] < 0） break;23.if （（n[i] - 3） % 4 == 0） nn.push_back（（n[i] - 3） / 4）, xx.push_back（x[i]）;24.}25.nn.push_back（maxn + 5）;26.while （scanf（"%I64d", &N）, N）27.{28.for （i = 0; i < nn.size（）; ++i）29.{30.if （N < nn[i]）31.{32.printf（"%I64d %I64d
", nn[i - 1], xx[i - 1]）;33.break;34.}35.}36.}37.return 0;38.}