问题:求$A = 1\times 3\times 5\times \dots \times 1989\times 1991$的末三位是?
解:
1、求解末3位相当于对1000求余。
2、$1000 = 125 \times 8 $,题目中A是奇数的乘积,肯定有125,故A是125的倍数。$A = 125 + 125 + 125 + … $,正好分完,没有余数,但因为是对1000求余,实际要这么分:$A = 125\times 8 + 125\times 8 + 125\times 8 + …$。由于 $奇数 \times 奇数 = 奇数$,故A不能整除8,会有余数。这个余数就是可能的末三位,由于奇数不能是偶数的倍数,故这个余数只能是奇数倍的125。也就是:125,475,625,875
3、故$A = 125 \times 8 + 125 \times 8 +…+ 125或475或625或875$,显然省略号前面都是8的倍数,后面4个余数对8的余数,决定了A模8是多少。分别可能是:5,3,1,3
4、再根据“余数的积等于积的余数”这条余数性质,得出A模8=1。
5、对A用2种不同的方法求了模8的余数,一致的只有余625的满足条件,所以该题A的余数是625。
总结:本题用到
1、余数三大性质。
2、奇偶性
3、奥数和计算机解题不同的只是数据规模,计算机更大了。但是解题逻辑是相同的。
但这些都不重要,它们只是作为一种工具存在,重要的是:拆分的思想,把一个整体拆分成细小的单元,根据题意加加减减,再重新组合成一个整体的思路。
最后,附上计算机程序,验证一下是否正确:
#include <cstdio>
using namespace std;
int main(){
int ans=1,p=1000;
for(int i=1;i<=1991;i+=2){
ans=ans*i%p;
}
printf("%d\n",ans);
return 0;
}