思路只有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 阅读(334)
评论(0) 编辑 收藏 引用