先算出p^3+q^3的所有的數,然後排序.同時為了加快後面的查詢,建立一個hash表.然後從頭開始枚舉每個數列的前2項,得到a和b,再判斷後面的幾項.要注意的一點就是數列可能會超過p^3+q^3的最大值.
#include<iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef struct
{
int a, b;
}Point;
Point p[1000];
int num;
bool comp(Point p1, Point p2)
{
if(p1.b!=p2.b)
return p1.b < p2.b;
else
return p1.a < p2.a;
}
int hash[300000];
int main()
{
int i, j, k;
int n, m, cnt,cas=0,temp;
int a[30000];
int flag = false;
while (cin >> n >> m)
{
if(n==0 && m==0)
break;
if(!flag)
flag = true;
else
cout << endl;
cnt = 0;
memset(hash, 0, sizeof(hash));
for (i=0; i<=m; ++i)
{
for (j=0; j<=m; ++j)
{
temp = i*i*i+j*j*j;
if(!hash[temp])
{
hash[temp] = 1;
a[cnt++] = temp;
}
}
}
num = 0;
int aa, bb;
sort(a, a+cnt);
for (i=0; i<cnt; ++i)
{
for (j=i+1; j<cnt; ++j)
{
aa = a[i];
bb = a[j] - a[i];
for (k=3;k<=n;++k)
{
int tte = aa+(k-1)*bb;
if(tte>a[cnt-1] || !hash[tte])
break;
}
if(k > n)
p[num].a = aa, p[num++].b = bb;
}
}
cout << "Case "<<++cas <<":"<< endl;
if(!num)
{
cout << "NONE" << endl;
continue;
}
sort(p, p+num, comp);
for (i=0; i<num; ++i)
{
cout << p[i].a << " " << p[i].b << endl;
}
}
return 0;
}
#include<iostream>#include <string>#include <algorithm>using namespace std;typedef struct {
int a, b;}Point;Point p[1000];int num;bool comp(Point p1, Point p2){ if(p1.b!=p2.b) return p1.b < p2.b; else return p1.a < p2.a; }int hash[300000];int main(){ int i, j, k; int n, m, cnt,cas=0,temp; int a[30000]; int flag = false; while (cin >> n >> m) {
if(n==0 && m==0) break; if(!flag) flag = true; else cout << endl; cnt = 0; memset(hash, 0, sizeof(hash)); for (i=0; i<=m; ++i) { for (j=0; j<=m; ++j) { temp = i*i*i+j*j*j; if(!hash[temp]) { hash[temp] = 1; a[cnt++] = temp; } } } num = 0; int aa, bb; sort(a, a+cnt); for (i=0; i<cnt; ++i) { for (j=i+1; j<cnt; ++j) { aa = a[i]; bb = a[j] - a[i]; for (k=3;k<=n;++k) { int tte = aa+(k-1)*bb; if(tte>a[cnt-1] || !hash[tte]) break; } if(k > n) p[num].a = aa, p[num++].b = bb; } } cout << "Case "<<++cas <<":"<< endl; if(!num) { cout << "NONE" << endl; continue; } sort(p, p+num, comp); for (i=0; i<num; ++i) { cout << p[i].a << " " << p[i].b << endl; } } return 0;}