首页 > ACM题库 > HDU-杭电 > HDU 2964-Prime Bases-最小生成树-[解题报告]HOJ
2014
02-24

HDU 2964-Prime Bases-最小生成树-[解题报告]HOJ

Prime Bases

问题描述 :

Given any integer base b >= 2, it is well known that every positive integer n can be uniquely represented in base b. That is, we can write

n = a0 + a1*b + a2*b*b + a3*b*b*b + …

where the coefficients a0, a1, a2, a3, … are between 0 and b-1 (inclusive).

What is less well known is that if p0, p1, p2, … are the first primes (starting from 2, 3, 5, …), every positive integer n can be represented uniquely in the "mixed" bases as:

n = a0 + a1*p0 + a2*p0*p1 + a3*p0*p1*p2 + …

where each coefficient ai is between 0 and pi-1 (inclusive). Notice that, for example, a3 is between 0 and p3-1, even though p3 may not be needed explicitly to represent the integer n.

Given a positive integer n, you are asked to write n in the representation above. Do not use more primes than it is needed to represent n, and omit all terms in which the coefficient is 0.

输入:

Each line of input consists of a single positive 32-bit signed integer. The end of input is indicated by a line containing the integer 0.

输出:

Each line of input consists of a single positive 32-bit signed integer. The end of input is indicated by a line containing the integer 0.

样例输入:

123
456
123456
0

样例输出:

123 = 1 + 1*2 + 4*2*3*5
456 = 1*2*3 + 1*2*3*5 + 2*2*3*5*7
123456 = 1*2*3 + 6*2*3*5 + 4*2*3*5*7 + 1*2*3*5*7*11 + 4*2*3*5*7*11*13

   这是一道比较简单的数学题=>题目地址

   题目大意:任意一个b进制的数,比如1234,可以有下面的式子成立:1234 = 4 + 3 * b + 2 * b * b  + 1 * b * b * b;现在规定一种特殊的进制,使得任意的整数n,都可以写成

n = a0 + a1 * p0 + a2 * p0 * p1……an * p0 * p1 *…*pn-1;期中a0,a1…是系数,p0….pn是从2开始的连续素数;给定的n为32位整数。

题目分析:此题是以连续的素数作为进制,所以关键求出各项系数。系数的求法我们不妨参照固定进制的整数求各个位的系数的方法。比如10进制下的1234:我们先用1234除以1000,得最高位1,1234模1000得234;234除以100得百位数字2,234模100得34;34除以10得十位数字3,34模10得4;4除以1得个位数字4,算法结束。于是1234 = 4 + 3 * 10 + 2 * 10 * 10 + 1 * 10 * 10 * 10;由于此题给的n是一个32为整数,所以素数表中只需要取13位就够了。详情请见代码:

#include <iostream>
#include<cstdio>

using namespace std;

int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41};//素数表

int n;

void dfs(__int64 num,int i)
{
    int nn;
    if(i == -1)
    {
        if(n)//最低位的数
            printf("%d",n);
        return;
    }
    int coefficient = n / num;//求系数
    n %= num;
    nn = n;
    if(n)//如果余数已经为0,就不必往下求了
        dfs(num / prime[i],i - 1);
    if(coefficient)
    {
        if(nn)
            printf(" + ");
        printf("%d",coefficient);
        for(int j = 0;j <= i;j ++)
            printf("*%d",prime[j]);
    }
}

int main()
{
    int i;

    while(scanf("%d",&n),n)
    {
        __int64 num = 1;
        for(i = 0;i < 13;i ++)
        {
            num *= prime[i];
            if(num > n)
            {
                num /= prime[i];
                break;
            }
        }
        i --;
        printf("%d = ",n);
        dfs(num,i);//求系数,并输出
        printf("\n");
    }
    return 0;
}

解题参考:http://blog.csdn.net/ophunter_lcm/article/details/8740131


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?