[理工] 离散 中国余数定理 鸽笼等

楼主: mistel (Mistel)   2019-11-24 22:34:47
有几个困扰已久的问题...
1.https://i.imgur.com/YB6AbA8.jpg
请问这题之所以mod8要换成mod4是因为
8|2x-4=2(x-2) => 4|x-2 这样吗?
2.https://i.imgur.com/ijPwwdh.jpg
https://i.imgur.com/XTn4PZ1.jpg
请问在彼此不互质是应该怎么判断才好?
像他说不可用2我完全不知道是为什么,
并请问为什么答案最后要取lcm(9,12,21)而不是取lcm(3,4,7)?
3.https://i.imgur.com/kC3vuqk.jpg
https://i.imgur.com/Dz84s5e.jpg
请问这题的b小题用到的鸽笼原理
两个蓝圈圈起来的上下句到底是怎么推得的?想好久...
作者: Ricestone (麦饭石)   2019-11-24 22:43:00
1.这里2跟8不互质,所以消的时候会连8一起变直接举例来说,因为2x=4mod8在mod8里面是有x=2跟x=6这两个结果2.不能用2就只是因为跟原本的联立方程式不等价而已而且这详解作法不对,mod9根本不用变只要确认7mod9跟另外那两个1mod3是相符的,那两个mod3就能去掉,所以剩的是mod9,mod4,mod7
作者: mathtsai (mathtsai)   2019-11-24 22:59:00
1.对 2.两两最大公因子不为1x = 12k+4 = 4*(3k+1) 如果用2来做 就不等价惹
作者: Ricestone (麦饭石)   2019-11-24 23:08:00
3.看不太懂你想问什么,不过2^(i-1)只有2的因子,而现在n已经说是奇数(没有因子2),所以当然互质
作者: mathtsai (mathtsai)   2019-11-24 23:21:00
3.写那么神秘干嘛...把你第一个蓝笔的部分相减得n | 2^j - 2^i = 2^i*(2^(j-i) - 1) => n | 2^(j-i)-1鸽笼其实某题会了 下次出神秘一点的一样没想法
作者: ok8752665 (dd8752665)   2019-11-24 23:27:00
离散一堆都是没看过根本没想法的==
作者: Ricestone (麦饭石)   2019-11-24 23:32:00
7mod9这个限制比1mod3来得强,有7mod9就不需要再讲mod3一个合数的同余式本来就有拆成等价的因子的联立同余式的办法,叫除法原理12本来就是拆成3跟4,如果用理论的想法,3跟4的余数可以表达12种情况,如果是3跟2就只剩6种,一定有问题用刚刚限制较强的想法也可以,4的限制就是比2多啊
作者: iamawinner (随风落脚)   2019-11-25 02:56:00
我是觉得,能2能整除的,4未必能整除
作者: zuchang (chang)   2019-11-25 12:24:00
楼上 那不就是4的限制比较大的意思吗:)

Links booklink

Contact Us: admin [ a t ] ucptt.com