首页 > ACM题库 > HDU-杭电 > HDU 3113-Sum of Cubes-DFS-[解题报告]HOJ
2014
03-02

HDU 3113-Sum of Cubes-DFS-[解题报告]HOJ

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?

Planet Alignment

输入:

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

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3113


题意:给出一个正整数n,范围是[1,1000000],求出满足方程Sum of Cubes的一组整数解,要求x最小。


分析:这个方程与平方和不同的是,加号两边的任意一个可以为负数,所以直接枚举然后Hash就显得不好做了。那么我用一种

比较有效的方式解决。


我们知道Sum of Cubes,那么我们这样来做,首先把n的所有因子找出来,枚举所有的因子。


假设当前的因子为Sum of Cubes,那么令Sum of Cubes,即得到:


Sum of Cubes


在这里其实还有一种情况就是:


Sum of Cubes


你会发现这种情况根本没有解,所以不予考虑。


对上面的方程组消去y,我们得到:Sum of Cubes ,那么得到:


Sum of Cubes


那么我们就只需要在枚举因子的过程中,判断Sum of Cubes是否为完全平方数和Sum of Cubes,并且记录最

小的x以及对应的y。


#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;
}


参考:http://blog.csdn.net/acdreamers/article/details/17096195


  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