原文链接：http://www.mydrs.org/program/list.asp?id=359
题目描述
把正整数k的所有方幂以及任意多个方幂之和排列成一个递增数列{a(k)}，求这个数列的第p项是多少
算法分析
这个数列的每一项可以写成
，其中，
，
且每一项其多项式的系数都符合二进制的变化规律。
引理1：对于任意整数k(k≥2)，m(m≥0)，一定有
证明：用归纳法，当m=0时，结论显然成立。设m=n时结论成立(n≥0)，即：
。所以，当m为任意非负整数时，结论均成立。
将整数k(k≥2)的所有方幂以及任意多个互不相等的k的方幂之和排成一个递增数列{a(k)}，将正整数p,转化成二进制形式：
，定义f(p) 表示 
。
引理2：若有两个正整数
,满足
，则一定有：
证明：将分别转化成二进制形式
，从高位向低位查找到第一个
，又
。所以，要证明引理2结论成立，只要证明
。而根据引理1的结论，有：
，又∵
，所以
，结论成立。
定理：递增数列{a(k)}中第p(p∈N+)大的数一定为f(p)。
证明：由引理2得知：任意i,j(i,j∈N+),若i 有了上述定理，我们就可以将p分解成二进制，得到下面形式： 注意：本题由于所得到的解可能很大（最大的解达到了31位），所以需要高精度。 程序如下： Const procedure work; 作者： 上一篇：SGOI-12友谊赛测试数据
且
刚好对应原多项式中每一项的
，,这时，只要将
的值代入，就可以得到所求数列第p项的数了。
InFile = 'AH02T6.in';
OutFile = 'AH02T6.out';
LimitLen = 70;
Type
lint = record
len : longint;
data : array[1..LimitLen] of longint;
end;
Var
K , P : longint;
result : lint;
procedure init;
begin
assign(INPUT , InFile); ReSet(INPUT);
readln(K , P);
Close(INPUT);
fillchar(result , sizeof(result) , 0);
result.len := 1;
end;
procedure add(var n1 , n2 : lint);
var
i , tmp ,
jw : longint;
begin
jw := 0; i := 1;
while (i <= n1.len) or (i <= n2.len) or (jw <> 0) do
begin
tmp := n1.data[i] + n2.data[i] + jw;
jw := tmp div 10;
n1.data[i] := tmp mod 10;
inc(i);
end;
n1.len := i - 1;
end;
procedure times(var n1 : lint; n2 : longint);
var
i , jw ,
tmp : longint;
begin
jw := 0; i := 1;
while (i <= n1.len) or (jw <> 0) do
begin
tmp := n1.data[i] * n2 + jw;
jw := tmp div 10;
n1.data[i] := tmp mod 10;
inc(i);
end;
n1.len := i - 1;
end;
var
now : lint;
i , N : longint;
begin
N := P;
fillchar(now , sizeof(now) , 0); now.len := 1; now.data[1] := 1;
while N <> 0 do
begin
if N mod 2 = 1 then
add(result , now);
N := N div 2;
if N <> 0 then
times(now, K);
end;
end;
procedure out;
var
i : longint;
begin
assign(OUTPUT , OutFile); ReWrite(OUTPUT);
for i := result.len downto 1 do
write(result.data[i]);
writeln;
Close(OUTPUT);
end;
Begin
init;
work;
out;
End.
来源：曙光
时间：2002-05-17
下一篇：《哈利·波特与魔法石》