求问余数规律题！例如3^50除以4这样的

Mintchoco

之前看过机经，有一类余数问题专门问一个整数的高次方除以另一个整数的余数是多少。
例如3^50除以4这样的。我知道如何找出余数的规律，但是下一步次幂的计算推理上有些混乱，能不能请NN们整理一些遇到的类似题目，并附上方法？谢谢NN们！

sheldooper

我忘记了从哪里看见的解法了，反正是这样解的：
3^50/4的余数你这么看，3^50=(4-1)^50,这就是1^50/4所以余数是1.
我不知道为啥，反正你被除数（3）往除数（4）那个数靠，然后出来多少就是多少就行了。

ukyo2003

我不知道这类题怎么解，但是在DS中经常考余数，有个小规律是被4除的余数不是1，2，就是3，哈哈。有时候会忘记这个，还是挺有用的

kikliojkl

sheldooper 发表于 2015-6-28 17:59
我忘记了从哪里看见的解法了，反正是这样解的：
3^50/4的余数你这么看，3^50=(4-1)^50,这就是1^50/4所以余 ...

这是mod的算法确切说是（8+1）^25mod4=1^25mod4=1

Mintchoco

kikliojkl 发表于 2015-6-28 23:36
这是mod的算法确切说是（8+1）^25mod4=1^25mod4=1

是每一个这种类型都可以吗？比如5^40除以3这样？

jptvhe

正确的解法是这样的
3^1个位数是3
3^2个位数是9
3^3个位数是7
3^4个位数是1
3^5个位数是3
3^6个位数是9
……
……
可以发现个位数的值是3971,3971四个一组这样循环的。
所以3^50的个位数=3^2的个位数=9
如果用这个数除以4，它的余数一定是1。
同理也可以应用在2^n，4^n，7^n等题目中。

Mintchoco

jptvhe 发表于 2015-6-29 11:14
正确的解法是这样的
3^1个位数是3
3^2个位数是9

找的就是这个方法！谢谢分享！

ukyo2003

赞一个

fencehuang

jptvhe 发表于 2015-6-29 11:14
正确的解法是这样的
3^1个位数是3
3^2个位数是9

同意！               

kikliojkl

Mintchoco 发表于 2015-6-29 00:52
是每一个这种类型都可以吗？比如5^40除以3这样？

是的 这是通用算法很简单 你可以搜一下mod的算法 在cd里面有人详细开贴讲解