我要招人

去企业版

首页 > 试题广场 >

给定两个数A、B（0，100000），求A^B中最后三位数是

[问答题]

给定两个数A、B（0，100000），求 A^B 中最后三位数是多少。请简要描述你的思路。

推荐

叶小鱼

//二分法求解
//a^b = (a ^ (b/2))^2
int GetPow(int a, int b) {
    if (b == 1 || b == 0) {
        return a % 1000;
    }
    if (b % 2) {
        return ((int) (GetPow((float) GetPow(a, b / 2), 2) * a) % 1000);
    } else {
        return ((int) (GetPow((float) GetPow(a, b / 2), 2)) % 1000);
    }
}

编辑于 2015-10-13 13:26:46 回复(5)

Echo001

//分治法求a^b，因为全部过程最多是三位数在运算，所以用int完全可以存储完全。
int getPow(int a,int b){
	if(b == 0){
		return 1;
	}else if(a <= 1 || b == 1)
		return a %1000;
	else if(b == 2){
		return a*a % 1000;
	}else if(b & 0x01 == 1){
		return (getPow(getPow(a,b/2),2)*a)% 1000;
	}else{
		return (getPow(getPow(a,b/2),2))% 1000;
	}
}

编辑于 2016-09-12 11:40:49 回复(0)

icebreaker

// 正解如下：先进行边界处理，然后二分
// 细节问题：getpow不能直接强转为int
double GetPow(int base, int power)
{
	if (power == 0)
		return 1;
	if (power == 1)
		return base;

	if (power % 2 == 0)
		return ((int) round((pow(GetPow(base, power / 2), 2))) % 1000);
	else
		return ((int) round((pow(GetPow(base, power / 2), 2) * base)) % 1000);
}

发表于 2015-09-07 18:31:02 回复(0)

陌上尘201807182102833

这个快速幂...就行了

发表于 2018-09-15 16:23:10 回复(0)

coco酱是个程序媛哟

class Solution():
    def lastThreeNums(self, a, b):
        if b == 0:
            return 1
        if b % 2 == 0:
            return pow(self.lastThreeNums(a, b/2), 2) % 1000
        else:
            return pow(self.lastThreeNums(a, int(b/2)), 2) * a % 1000

编辑于 2015-09-07 20:59:47 回复(0)

YvY

10000/2=5000余0

5000/2=2500余0

2500/2=1250余0

所以100000后三位000，0后三位000所以^后三位000

发表于 2015-08-18 17:13:11 回复(0)

牛客340044号

循环Ｂ次乘法。。每次只算最低三位。每次的结果也只保留３位。

发表于 2015-04-01 18:09:39 回复(1)

REDStone

0用二进制表示为000000000000000，

1000000用二级制表示为。。。。。。。

然后异或一下就OK了

发表于 2014-11-22 23:17:31 回复(0)

提交观点

问题信息

C++工程师 C++ Java 智力题百度 2011 Java工程师

来自：百度2011研发工程师笔试卷

难度：

8条回答 90收藏 11734浏览

给定两个数A、B（0，100000），求A^B中最后三位数是

问题信息

热门推荐

相关试题