网络传输

题目描述

　　把正整数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<j，则一定有f(i)<f(j)，即f(1)<f(2)<f(3)…，又∵集合{a(k)}包含且仅包含f(i) (i∈N+)，因而结论成立。

　　有了上述定理，我们就可以将p分解成二进制，得到下面形式：
　　　　　　　　　　　　　　　
且 刚好对应原多项式中每一项的，,这时，只要将的值代入，就可以得到所求数列第p项的数了。

注意：本题由于所得到的解可能很大（最大的解达到了31位），所以需要高精度。

程序如下：

Const
　　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;

procedure work;
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.