求a的b次方个位数字是多少??(a,b都为大数)
小弟做ACM的时候遇到了个问题~
那就是求a的b次方个位数字是多少
即a^b的个位数.
当然,正整数a和b都可能是大数..但都不超过100位
如果a是大数,而不是大数..小弟偶倒想出了算法..不过也很麻烦的说..
现在a,b都是大数了~~
不知道该用什么算了~~
thx 4 helping~~
[解决办法]
相当于是 对b做一个大数减法 ，
控制一个 1位数 的累乘 就可以了 ～
大数减法，
这个比较简单，就不需要说了吧，
如果不明白，
Google搜索 大数运算
[解决办法]
个位是0,1,5,6的个位结果还是0,1,5,6
个位是2的以 2,,4,8,6 循环
3:以3,9,7,1循环
4:以4,6循环
7: 7,9,3,1循环
8: 8,4,2,6循环
9: 9,1循环
循环次数分别为1,4,4,2,4,4,2 最小公倍数是4
所以a^b的个位数与 a^(b%4)的个位是相同的
现在的问题是b是个大数,b%4不好算
其实也好算,取b的后2位就行了也就是个位数和10位数, 因为b=b/100+b%100=b/25/4+b%100,所以(b%100)%4==b%4
