BNU 3209 Visible Lattice Points
题目大意：在n*n的图中有多少点与原点连线不会被其他点与原点的连线重叠。
分析：解题思路：欧拉函数
在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。
φ函数的值 Euler函数通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。#include<iostream> #include<string.h> #include<math.h> using namespace std; int n; int euler(int x) { int i,j,k; int a,b; a = x; k = (int)sqrt((double)x); for(i = 2; i <= k; i++) if(x % i == 0) //是其因子 { while(x % i == 0) x = x / i; //求出质因子 a = (a/i)*(i-1); } if(x != 1) a = (a/ x)*(x-1); return a; } int main() { freopen("input.txt","r",stdin); int i,t; int cases,sum; scanf("%d",&cases); for( t=1;t<=cases;t++) { scanf("%d",&n); sum = 0; for(i = 2; i <= n; i++) sum += euler(i); sum = sum*2 + 3; //(3个分别为x轴上，y轴上，还有一个(n，n)) printf("%d %d %d/n",t,n,sum); } }
