| |
|
算法
容易看出：客人到来的情况是无关紧要的，也就是说：有用的只是m,n,k这三个数。
如果利用简单的动态规划，在时间上是无法承受的。但是却可以得到一些m、n、k不太大时的结果，帮助我们找到规律。
经过观察，发现：本题的答案就是
现在关键在于计算 ，约分后写成 ……的形式（ 为质数）。为了加快速度，采用二分法求乘幂、一位保存多位优化高精度，就可以在时限内出来了。
参考程序
{$r-,s-,q-}
const
finp = 'dance.in';
fout = 'dance.out';
maxn = 10000;
digits = 8;
maxvalue = 100000000.0; {pow(10, digits)}
maxll = 10000;
maxkk = maxll div digits + 1;
type
TBigNumber = record
l: integer;
num: array[1 .. maxkk] of comp;
end;
var
x: array[1 .. maxn] of byte;
w: array[1 .. maxn] of integer;
i, j, k, l, n, m, q, maxlen, maxk: integer;
r, pp: TBigNumber;
rr: array[1 .. maxkk] of comp;
v, p: comp;
s: string;
begin
assign(input, finp);
reset(input);
readln(n, m, maxlen);
close(input);
maxk := maxlen div digits + 1;
fillchar(x, sizeof(x), 0);
for i := 2 to trunc(sqrt(n)) + 1 do
if x[i] = 0 then
begin
k := i * i;
while k <= maxn do
begin
x[k] := i;
k := k + i;
end;
end;
fillchar(w, sizeof(w), 0);
for i := n - m + 1 to n do
w[i] := w[i] + 2;
for i := 1 to m do
w[i] := w[i] - 1;
for i := n downto 1 do
if x[i] <> 0 then
begin
w[x[i]] := w[x[i]] + w[i];
w[i div x[i]] := w[i div x[i]] + w[i];
w[i] := 0;
end;
if w[2] < w[5] then
i := w[2]
else
i := w[5];
w[2] := w[2] - i;
w[5] := w[5] - i;
r.l := 1;
r.num[r.l] := 1;
for m := n downto 2 do
if w[m] <> 0 then
begin
pp.l := 1;
pp.num[pp.l] := m;
q := w[m];
while q and (q - 1) <> 0 do
q := q and (q - 1);
k := 1;
while q > 1 do
begin
fillchar(rr, sizeof(rr), 0);
l := pp.l;
i := 1;
while i <= l do
begin
p := pp.num[i];
k := i shl 1 - 1;
rr[k] := rr[k] + p * p;
p := p + p;
i := i + 1;
for j := i to l do
begin
k := k + 1;
rr[k] := rr[k] + p * pp.num[j];
end;
if k = maxk then
l := l - 1;
end;
l := l + pp.l;
if l > maxk then
l := maxk;
p := 0;
for i := 1 to l do
begin
v := rr[i] + p;
p := int(v / maxvalue);
pp.num[i] := v- p * maxvalue;
end;
if pp.num[l] = 0 then
l := l - 1;
q := q shr 1;
if w[m] and q <> 0 then
begin
p := 0;
for i := 1 to l do
begin
v := pp.num[i] * m + p;
p := int(v / maxvalue);
pp.num[i] := v - p * maxvalue;
end;
if (l < maxk) and (p <> 0) then
begin
l := l + 1;
pp.num[l] := p;
end;
end;
pp.l := l;
end;
l := r.l;
fillchar(rr, sizeof(rr), 0);
for i := 1 to pp.l do
begin
p := pp.num[i];
k := i;
for j := 1 to l do
begin
rr[k] := rr[k] + p * r.num[j];
k := k + 1;
end;
if k = maxk + 1 then
l := l - 1;
end;
l := l + pp.l;
p := 0;
for i := 1 to l do
begin
v := p + rr[i];
p := int(v / maxvalue);
r.num[i] := v - p * maxvalue;
end;
if r.num[l] = 0 then
r.l := l - 1
else
r.l := l;
end;
fillchar(x, sizeof(x), 0);
str(r.num[r.l] : 0 : 0, s);
l := length(s);
for i := 1 to l do
x[i] := byte(s[i]);
for i := r.l - 1 downto 1 do
begin
str(r.num[i] : 0 : 0, s);
while length(s) < digits do
s := '0' + s;
for k := 1 to length(s) do
x[(r.l - i - 1) * digits + l + k] := byte(s[k]);
end;
l := (r.l - 1) * digits + l;
k := 1;
while (l - k + 1 > maxlen) or (x[k] = ord('0')) do
k := k + 1;
assign(output, fout);
rewrite(output);
for i := k to l do
write(char(x[i]));
close(output);
end.
|
|
|
