Question

一道pascal问题，还有一个地方不对，应该怎么改正？

正整数里面的每位数字相乘,比如：6593。将这个整数中的各位数字全部取出，将他们相乘，得到一个新的整数，上面的例子就是6*5*9*3=810，然后继续做下去，8*1*0*=0得到了一个个位数0。
问最后剩下的个位数字是几？
输入：
98886
输出：
0 注意这个数的位数(2<=l<=100)！
var
s:string;
function multi(s:string):string;
var
t:qword;
i:longint;
begin
t:=1;
for i:=1 to length(s) do
begin
if s[i]<>'0' then t:=t*(ord(s[i])-48);
end;
str(t,multi);
end;
begin
readln(s);
while length(s)<>1 do s:=multi(s);
writeln(s);
end.
这道题方法我觉得很好，但是当这个s的位数乘起来之后大于了qword的范围了那应该怎么办啊？可以用string来解决吗？

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏30（财富值+成长值）

Answer 1

　　LZ你好，又是我。
　　在算法竞赛中，凡是涉及个位数的题目，都应该考虑：会不会爆数据类型！能不能只算个位数字！通常都是：会啊！能啊！

你能将每次乘法得出的结果对10取模，只留下个位数字就行了。如果要程序可以追问（写pascal真的不太习惯……）

追问

mod 10？？？这样不会错吗？

追答

噢噢我看错题了
请问具体数据规模，你说的2<=l<=100是指输入数据还是求得的乘积？

追问

l是他的位数

我的意思是说这个字符串的位数为一百

只是不知道怎样运用字符串的加减

追答

　　该不会是高精度乘法吧……像这种题初看时有两种考察可能：考察编程基础（高精度运算）、考察数学基础（建模）。

　　可以使用高精度乘法来做，算法是模拟。

　　建模的话我现在想想……你留下个追问好让我再回答

高精度运算：

• 其根本是用一个数组存储一个数，以达到存储一个非常大的数的目的（但是很浪费空间，计算也很慢）

• 用一个数组a来表示一个大数，习惯上a[0]表示该数的位数，a[1]表示个位，a[2]表示十位，以此类推。

• 高精度加法、乘法、除法、减法分别使用4个函数（或者过程）来实现，网上很多代码。也可以尝试不看代码自己编，提示：草稿纸写竖式
  

追问

嗯嗯，到时这道题确实可以用字符串来解答，您可以只帮我解释一下吗？

追答

• 首先明确：999…999（两百个9），每个9拆开相乘，积不超过200位，因此定义数组a[0..200]来存储这个大数。

• 输入仍然用string类型，这里用变量s。a[0] = length(s); a[1..a[0]]分别取s的个位（最后一位）、十位（倒数第二位），以此类推。

• 因为我们每次乘法都是一个多位数乘一个个位数，所以我们使用 高精度乘单精度 的技巧。

　　高精度乘单精度 步骤：

1. 定义：因数（大数）为数组a，因数（小于10的数）为整型b，积（大数）为数组c。

2. 已经有a和b。c数组清0，但是c[0] := 1（也可以不管，但是为了严谨）。

3. for i := 1 to a[0]， 即枚举a的位数，从个位开始，对应地c[i] := a[i]*b + c[i];    此时c[i]有可能大于等于10了，若如此，c[i+1] = c[i] div 10且c[i] = c[i] mod 10，这也是为什么c[i]不单纯地等于a[i]*b，因为有进位（可参考乘法竖式）

4.   结束for后，检查c的位数，两种情况：1) c[0] = a[0]   2) c[0] = a[0]+1，用if判断即可。

5. a:=c，积就是a（或者c，但习惯上c是临时的，会因函数的结束而消失）

　　如何解决此题（建议不要看）：

1. 输入s，用s来初始化a。

2. 新建临时大数t，t初始化为a[1]，然后用高精度乘单精度计算 t := t*a[2]; t:=t*a[3]……

3. a:=t;

4. 若a[0] = 1 ，输出a[1]，否则转2.

追问

可是我现在还没学过高精度啊。。。可以不用吗？

追答

　　不能不用呀。我已经考虑过数学建模了，建不起。
　　请看例子： 66 -> 36 -> 18 -> 8， 如果我的电脑存不起66、36、18这样的“大数”，只能存个位数（这是夸张，但容易理解），就意味着我有两种选择：1）高精度存贮66、36、18 ；2）投机取巧，一步登天，直接由字符串“66”得到答案8。但是66和8都没什么关系。
　　如果用逆向思维，可以想到0到9这十个答案分别对应着十个不相交的自然数集合（就是每个输入的输出唯一啦），能不能分析这十个自然数集合的特点呢？答案是有可行性，但是费时太多了，远比学习高精度乘单精度来的难。
　　你要代码我可以无偿写，还有详细注释。这题明摆着让你克服高精度的。

追问

请看私信