2014
02-24

# 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位整数。

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

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