ChaseDream
搜索
返回列表 发新帖
楼主: zhlee
打印 上一主题 下一主题

余数题通解V2.0

[精华]   [复制链接]
11#
发表于 2010-10-21 00:46:23 | 只看该作者
好贴,别沉
12#
发表于 2010-10-21 03:16:30 | 只看该作者
不互质如何
13#
发表于 2010-10-21 03:17:36 | 只看该作者
如果超出欧拉定理的适用范围, a 和n 不互质, 该怎么办呢?
-- by 会员 tinnashen (2010/10/20 4:55:03)







这位同学的问题也是我的问题,如果a,n不互质,应该如何。
14#
 楼主| 发表于 2010-10-21 12:18:03 | 只看该作者
如果超出欧拉定理的适用范围, a 和n 不互质, 该怎么办呢?
-- by 会员 tinnashen (2010/10/20 4:55:03)



约分呀,约到互质不就可以了?


不过别忘了最后要把余数再乘以被约掉的数。不过你见过余数题上来先约分的么?


求: 3^7 除以 15 的余数

除数和被除数都除以3, 约分以后 ,先求 3^6 除以 5 的余数,


按照上面的方法,算出来余数是4,
再把余数成以约分的数 3

所以 3^7 除以 15 的余数 是 12


这种题目出现的可能性几乎为0
15#
发表于 2010-10-21 13:31:24 | 只看该作者
再来个超精简版
第一步,换底数——底除以除数后的余数
第二步,换指数——指数的欧拉数
第三步,硬算^_^
16#
 楼主| 发表于 2010-10-21 14:02:18 | 只看该作者
第三部 硬算

如果硬算的计算量大,是可以偷懒的,因为乘法和幂运算都是可以取余数的。

比如我来硬算一下 3^7 除以 15的余数

3^7
= 3*(3^3^2)
= 3*27^2
= 3*(15+12)^2
≡ 3*12*12
= 36*12
= (30+6)*12
≡ 6*12
=3*24
≡ 3*9
= 27 ≡ 12 (mod 15)
17#
发表于 2010-10-23 15:43:50 | 只看该作者
小女不才,不怎么看的懂。。。
18#
发表于 2010-10-25 09:40:05 | 只看该作者
呃。。。。。。。。同看不懂
19#
 楼主| 发表于 2010-10-25 10:18:51 | 只看该作者
看不懂1楼的直接看4楼和5楼就可以了。
20#
发表于 2010-10-28 11:00:12 | 只看该作者
太牛了,不過要弄懂就要華很久的時間,我還是放弃了
您需要登录后才可以回帖 登录 | 立即注册

Mark一下! 看一下! 顶楼主! 感谢分享! 快速回复:

手机版|ChaseDream|GMT+8, 2024-11-20 10:37
京公网安备11010202008513号 京ICP证101109号 京ICP备12012021号

ChaseDream 论坛

© 2003-2023 ChaseDream.com. All Rights Reserved.

返回顶部