求13的13次方的最后三位数?

[复制链接]
1131|6
 楼主| 给力芯片 发表于 2015-10-29 23:32 | 显示全部楼层 |阅读模式
求13的13次方的最后三位数?
peace555 发表于 2015-10-29 23:34 | 显示全部楼层
解本题最直接的方法是:将13累乘13次方截取最后三位即可。
但是由于计算机所能表示的整数范围有限,用这种“正确”的算法不可能得到正确的结果。事实上,题目仅要求最后三位的值,完全没有必要求13的13次方的完整结果。
研究乘法的规律发现:乘积的最后三位的值只与乘数和被乘数的后三位有关,与乘数和被乘数的高位无关。利用这一规律,可以大大简化程序。
zheng522 发表于 2015-10-30 10:41 | 显示全部楼层
#include<stdio.h>
int main()
{
int i,x,y,last=1; /*变量last保存求X的Y次方过程中的部分乘积的后三位*/
printf("Input X and Y(X**Y):");
scanf("%d**%d",&x,&y);
for(i=1;i<=y;i++) /*X自乘Y次*/
last=last*x%1000; /*将last乘X后对1000取模,即求积的后三位*/
printf("The last 3 digits of %d**%d is:%d\n",x,y,last%1000); /*打印结果*/
}
zheng522 发表于 2015-10-30 10:42 | 显示全部楼层
*运行结果
Input X and Y(X**Y):13**13
The last 3 digits of 13**13 is:253
Input X and Y(X**Y):13**20
The last 3 digits of 13**20 is:801
boy1990 发表于 2015-12-16 17:08 来自手机 | 显示全部楼层
不错,学习了,这种算法还挺巧妙的啊。
布谷鸟2015 发表于 2015-12-16 17:12 来自手机 | 显示全部楼层
好深奥啊,都看不懂了。。。。
sourceInsight 发表于 2015-12-16 17:18 来自手机 | 显示全部楼层
膜拜啊!!!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

65

主题

624

帖子

0

粉丝
快速回复 在线客服 返回列表 返回顶部