找出N*N范围内可见格点的个数.
只考虑下半三角形区域,可以从可见格点的生成过程发现如下规律:
若横纵坐标c,r均从0开始标号,则
(c,r)为可见格点 <=>r与c互质
证明:
若r与c有公因子1<b<min(r,c),则(c/b, r/b)在线段(0, 0)(c, r)上,则(c, r)不是可见格点.(充分性)
若r与c互质,显然线段上不存在整点,则(c, r)不是可见格点.(必要性)
φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值
也就是横坐标增1后纵坐标合法数目,即新增可见格点数(下半三角形区域).用时应乘二.
#include<stdio.h>
#include<str......
阅读全文