学步园

Sum of Cubes

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 815    Accepted Submission(s): 182

Problem Description

According to Goldbach’s conjecture, every even number can be expressed as a sum of two odd primes. Which numbers can be expressed as the sum of two cubes?

 

 

Input

For each test case, a line will contain a positive integer n which will be at most one million.

The last line will contain the integer 0, which should not be processed.

 

Output

For each test case, output two integers x and y such that x³ + y³ = n. If there are many such pairs of numbers, choose x to be as small as possible. If there are no such pairs, output “Impossible”.

Sample Input

1

2

3

1000000

0

 

Sample Output

0 1

1 1

Impossible

0 100

 

Source

IPCP 2005 Northern Preliminary for Northeast North-America

 

Recommend

lcy

 

#include<iostream>
using namespace std;
const int maxn=1000000,inf=10000;
struct Cube{
    int x,y;
};
Cube cube[maxn+1];
int flag[maxn+1];
int main(){
    //freopen("in.txt","r",stdin);
    memset(flag,0,sizeof(flag));
    for(int i=0; i<=maxn; i++){
        cube[i].x=inf;
        cube[i].y=inf;
    }
    for( int i=-800;i<=800;i++){
        for(int j=-800;j<=800;j++){
            int temp=i*i*i+j*j*j;
            if(temp>=0 && temp<=maxn && i < cube[temp].x){
                flag[temp]=1;
                cube[temp].x=i;
                cube[temp].y=j;
            }
        }
    }
    for(int n;cin>>n && n;){
        if (flag[n]==0)
            cout<<"Impossible\n";
        else
            cout<<cube[n].x<<' '<<cube[n].y<<'\n';
    }
}

用傻逼的方法生成n(n=x^3+y^3)，存到数组里,把范围改到800才过，原先的计算错了以为200^3-199^3>10^6，把范围写成200，结果还有可能出现更小的x.

悲剧。。。