笔试题:712的729次方的最后4位数是多少?

问题：设计一个程序，求出712的729次方的最后4位数是多少？
大整数相乘问题,不能简单的乘,早就溢出了.所以要另辟蹊径.在相乘时每次取出后四位其余丢弃,不影响最后的四位数.
源代码如下：

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
int value = 1;
for(int i=1;i<=729;++i)
{
value*=712;
value%=10000;
}
//设置输出格式,4位,用0填充.
cout<<setw(4)<<setfill('0')<<value<<endl;
system("pause");
return 0;
}

如果我们注意到729 = 3^6,可以减少循环次数.

#include<stdio.h>
int main()
{
unsigned long long a3 = (712*712*712)%10000;
unsigned long long a9 = (a3 *a3*a3)%10000;
unsigned long long a27 = (a9 *a9*a9)%10000;
unsigned long long a81 = (a27 *a27*a27)%10000;
unsigned long long a243 = (a81 *a81*a81)%10000;
unsigned long long a729 = (a243 *a243*a243)%10000;
printf ("result=%d \n",a729);
getchar();
return 0;
}

文章转载自:我爱程序员 www.52coder.net

2楼han_yankun200948分钟前

学习了

1楼qiji_20091小时前

看了这题目 知道算法的重要性了！