2014
03-02

# Sum of Cubes

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?

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.

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.

1
2
3
1000000
0

0 1
1 1
Impossible
0 100

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
const int N = 1000005;
const int INF = 1 << 30;
const int M = 1005;

bool prime[N];
int p[N];
int pri[M],num[M];
int arr[M];
int k,cnt,ct;

void isprime()
{
k = 0;
memset(prime,true,sizeof(prime));
for(int i=2;i<N;i++)
{
if(prime[i])
{
p[k++] = i;
for(int j=i+i;j<N;j+=i)
prime[j] = false;
}
}
}

void Divide(int n)
{
cnt = 0;
int t = (int)sqrt(1.0*n);
for(int i=0;p[i]<=t;i++)
{
if(n%p[i]==0)
{
int a = 0;
pri[cnt] = p[i];
while(n%p[i]==0)
{
n /= p[i];
a++;
}
num[cnt] = a;
cnt++;
}
}
if(n > 1)
{
pri[cnt] = n;
num[cnt] = 1;
cnt++;
}
}

void dfs(int dept,int product = 1)
{
if(dept == cnt)
{
arr[ct++] = product;
return;
}
for(int i=0;i<=num[dept];i++)
{
dfs(dept+1,product);
product *= pri[dept];
}
}

void Work(int n)
{
ct = 0;
Divide(n);
dfs(0,1);
sort(arr,arr+ct);
int ctt = 0;
int ansx = INF;
int ansy = INF;
int tmpx = 0;
int tmpy = 0;
for(int i=0;i<ct;i++)
{
int t = n / arr[i] * 12 - 3 * arr[i] * arr[i];
if(t >= 0)
{
int tmp = (int)sqrt(t * 1.0);
if(tmp * tmp == t)
{
if((3*arr[i] - tmp)%6==0)
{
ctt++;
tmpx = (3*arr[i] - tmp) / 6;
if(tmpx < ansx)
{
ansx = tmpx;
ansy = arr[i] - tmpx;
}
}
if((3*arr[i] + tmp)%6==0)
{
ctt++;
tmpx = (3*arr[i] + tmp) / 6;
if(tmpx < ansx)
{
ansx = tmpx;
ansy = arr[i] - tmpx;
}
}
}
}
}
if(ctt == 0) puts("Impossible");
else printf("%d %d\n",ansx,ansy);
}

int main()
{
int n;
isprime();
while(~scanf("%d",&n))
{
if(n == 0) break;
Work(n);
}
return 0;
}

1. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count