首页 > ACM题库 > HDU-杭电 > hdu 2281 Square Number-数论应用-[解题报告]C++
2014
01-05

hdu 2281 Square Number-数论应用-[解题报告]C++

Square Number

问题描述 :

Find the biggest integer n (1 <= n <= N) and an integer x to make them satisfy

输入:

The input consists of several test cases. Each test case contains a integer N, 1<=N<=10^18.The input ends with N = 0.

输出:

The input consists of several test cases. Each test case contains a integer N, 1<=N<=10^18.The input ends with N = 0.

样例输入:

1
2
0

样例输出:

1 1
1 1

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中,详见代码。

完整代码:

/*31ms,276KB*/

#include<cstdio>
#include<vector>
using namespace std;
typedef __int64 ll;
const ll maxn = 1e18;

ll n[20], x[20];
vector<ll> nn, xx;

int main()
{
	int i;
	long long N;
	n[0] = 7LL, x[0] = 1LL;
	nn.push_back(1LL), xx.push_back(1LL);
	for (i = 1;; ++i)
	{
		n[i] = 7LL * n[i - 1] + 48LL * x[i - 1];
		x[i] = n[i - 1] + 7LL * x[i - 1];
		if (n[i] < 0) break;
		if ((n[i] - 3) % 4 == 0) nn.push_back((n[i] - 3) / 4), xx.push_back(x[i]);
	}
	nn.push_back(maxn + 5);
	while (scanf("%I64d", &N), N)
	{
		for (i = 0; i < nn.size(); ++i)
		{
			if (N < nn[i])
			{
				printf("%I64d %I64d\n", nn[i - 1], xx[i - 1]);
				break;
			}
		}
	}
	return 0;
}

解题转自:http://blog.csdn.net/synapse7/article/details/16994157


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的