posts - 24,  comments - 0,  trackbacks - 0
思路只有bfs,可是分类在数学里,所以极力寻求数学方法,分析在这里

http://www.cnblogs.com/devymex/archive/2010/08/04/1792288.html

下面简单证明: 当n从0到B-1变化时,r可以取到0到B-1之间的任何值
用反正法:
na % B可以取到的值只有 0 ~ B-1, 当n从0 ~ B-1时,假设r不能取完0 ~ B-1, 则必有n取两个不同值时% B值相同,
设为n1,n2;则n1A % B = x,n2A % B = x, 两边分别相比,得 n1 / n2 = 1, 即 n1 = n2, 与假设矛盾,证毕!!

PS: a 和 b 互质说明什么? 说明gcd(a,b) = 1 && lcm(a,b) = a * b && for n <- 0 ~ b - 1   n * a % b 可以取到 0 ~ b - 1;
posted on 2012-04-25 19:47 ACSeed 阅读(282) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

常用链接

留言簿(1)

随笔档案

偶像的Blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜