Question

pascal如何打表？

经常在noip的骗分技巧上有看到打表这个词，求教到底如何打表？
打表的格式是怎样的？
是要在纸张上用手算，然后输入到程序中，还是编个有什么特点格式的程序？
第二种要如何暴力搜索？

例题就用回文素数（可逆素数）吧。
求a-b之间所有可逆素数。可逆素数是指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数。例如1009为素数，它的反序数9001也是素数，所以1009是可逆素数。这里我们规定可逆素数比它的反序数小，即1009是可逆素数，而9001不算可逆素数。

这里编程菜鸟求助~
谢谢。
数据范围a,b<=10000
最好有暴搜的程序范例。
是不是先编一个程序，将答案保存在txt上，再复制到新的打表程序上？
打表的数据个数有限制么？

Answer 1

打表是一种抽象的概念，它不一定是贬义词。因为有些题目的正解的确是所谓的“打表”

打表的方法主要由数据范围决定：

①题目数据范围极小，编程复杂度极高，此时可以手算得出所有数据的答案。

②题目数据范围大，手算难以算出结果，打一个暴力枚举程序，尤其在某些数论题目中适用，求出每一个可能的值的结果。

③打表不一定是骗分，某些题目需要在读入数据前预处理出解题需要的条件，而这样往往会比读入一个求一个更优。

打表的技巧：

①使用前缀和优化，某些题目可能会限制代码长度，此时可以用这一项的值减去前一项的值去优化表。

②使用分段打表技巧，每隔一段距离就记录一个数值，这样利用离询问最近的值去推答案，会大大优化时间复杂度，但这样前提是答案会具有递推性质，即后一项是由前一项或前一项是由后一项推出来的。

本题可以打一个暴力程序（如果max b 不大的话），记录下所有可逆素数，开一个数组储存，即

ans:array[1..maxn]of longint=( , , , , , , , , , , ,);

或者存下所有范围内的素数，确定在区间[a,b]内的质数后一一枚举配对。

在正式比赛时可以使用打表的方法，但是在平时训练时不推荐使用，因为如果你养成了一种依赖打表来获取部分分的习惯，就不会去想正解。所以，这种方法，还是少用好。

追问

打表技巧1，2点是什么意思？能有个示范程序么？

追答

比如说，题目要求求出第i个质数，朴素的打表方法是

prime:array[1..10000]of longint=(2,3,5,7,11,13,17,19,23,29,31,37......);

但我们可以将其改为

prime:array[1..10000]of longint=(2,1,2,2,4,2,4,2,4,6,2,6......);

求第n个质数时可以

for i:=1 to n do
    sum:=sum+prime[i];

sum即为答案

分段打表：f(x)=(f(x-1)*5+1000) div 2 mod 10000007

在x很大的情况下，我们很难及时去求出结果，所以可以打一个暴力程序求出

f(0),f(2000000),f(4000000),f(6000000),f(8000000)......复制到程序上，每次从f(x) (x<=n且最大)开始算起，可以大大节省时间。

追问

非常感谢。
请问,1,2,2,4,2,4,2,4,6,2,6这些数是怎么得出的？
分段打表f(x)=(f(x-1)*5+1000) div 2 mod 10000007是什么意思？
每次从f(x) (x<=n且最大)开始算起，是不是将f(8000000)复制到程序上后，下一次直接算从8000001到10000000？

追答

设p[i]为第i个质数，f[i]就是p[i]-p[i-1](p[0]:=0)

f(x)=(f(x-1)*5+1000) div 2 mod 10000007是一个递推式，就和斐波那契数列f[i]=f[i-1]+f[i-2]是差不多的。。。

将暴力程序算好的f(0),f(2000000),f(4000000),f(6000000),f(8000000)......复制到程序上

f:array[0..maxn]of longint=(f(0)的值,f(2000000)的值,f(4000000)的值......)

比如说读入10000，那就从f(0)算起，读入5000000，就从f(4000000)算起

Answer 2

1：文件的用法
一般情况下，最简单的是在主程序的最前面加上这样几句
assign(input,'文件名');
reset(input);
assign(output,'文件名');
rewrite(output);
程序的最末尾加上：
close(input);
close(output);
2：打表
打表是用于一些输入的范围很小的时候使用的，打表最简单的形式如：
const a:array[1..maxn] of longint=(...)
var i:longint;
begin
readln(i);
writeln(a[i]);
end.
其中常数中省略的部分既是题目要求的表，例如输入N，求圆周率小数点后的第N位，maxn为N的最大值，后面的表的第i位，既是圆周率的第i位。
但是要注意，因为是打表，所以要手工输入，所以当数据多时，不建议打表。
希望能解决您的问题。

追问

不要复制好吗？
我就是问常数中省略部分那么大的一长串数怎么来的？