| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大家帮我看看,请提供测试数据,谢谢郁闷,还是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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator