首页 > 代码库 > 数论的一些小结论
数论的一些小结论
1.有两个数p,q,且gcd(q,p)=1,则最大无法表示成px+qy(x>=0,y>=0)的数是pq-q-p(对于n>pq-q-p,都可以表示成px+qy;而pq-q-p,就无法表示成px+qy)。
2.皮克定理说明了顶点是整点的多边形面积S和内部格点数目a、边上格点数目b的关系:S = a + b/2 - 1。
3.一条直线((0,0),(n,m))上的格点数等于n与m的最大公约数+1。
证明:
记n,m最大公约数k,m=ak,n=bk,那么(a,b)=1
考察(0,0)到(m,n)直线上一个格点(x,y)(x>0,y>0),有:
x/y=m/n=a/b
即bx-ay=0
因gcd(a,b)=1,必有b|y,a|x,再由x≤m,y≤n,知这样的x,y有k个
加上(0,0)点,所有的格点数=k+1,得证
数论的一些小结论
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。