Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大家帮我看看,请提供测试数据,谢谢

Posted by duloc at 2006-10-22 02:36:21 on Problem 2100
郁闷,还是WA,大家帮我看看
一开始没注意10^14,然后又选了c++,最后才发现要选g++,不过还是WA
我的思想很简单:
如果
an^2 +bn + c = 0,有正数解
说明:
total = n^2 + (n+1)^2 + (n+2)^2 + ... + (n+a-1)^2
终止条件是c>=0。
b,c的值依a, total而定。
谢谢了。
=================================================

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

typedef long long int int64b;

struct __a_result {
	int64b start;
	int64b count;
};
typedef struct __a_result a_result;

vector<a_result> results;

int main()
{
	int64b total;
	int64b a, b, c, d;
	int64b n;
	a_result ares;

	cin >> total;
	
	a = 1;
	b = 0;
	c = 0 - total;
	d = 0;
	while (true) {
		b += (a << 1);
		d += (a << 1) - 1;
		c += d;
		if (c >= 0) {
			break;
		}
		a++;
		// solve the function 
		//         a*n^2 + b*n + c = 0
		// for an integer value.
		int64b delta = b * b - 4 * a * c;
		int64b delta_root = (int64b)sqrt(delta);
		if ((delta_root * delta_root) != delta) {
			continue;
		}
		int64b s = delta_root - b;
		if (s <= 0) {
			continue;
		}
		if ((s % (2 * a))) {
			continue;
		}
		n = s / (2 * a); 

		ares.start = n;
		ares.count = a;

		results.push_back(ares);
	}
	
	b = results.size();
	cout << b << endl;
	for (a = b - 1; a >= 0; a--) {
		a_result &arr = results.at(a);
		cout << arr.count << " ";
		for (c = arr.start; c < arr.start + arr.count - 1; c++) {
			cout << c << " ";
		}
		cout << c << endl;
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator