| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5136 | Accepted: 2985 |
Description
A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.
Write a program which, given a value for the size, N, computes the number of visible points (x< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvZW0+LCA8ZW0+PHN0cm9uZz55PC9zdHJvbmc+PC9lbT4pIHdpdGggMCCh3CA8ZW0+PHN0cm9uZz54PC9zdHJvbmc+PC9lbT4sIDxlbT48c3Ryb25nPnk8L3N0cm9uZz48L2VtPiCh3CA8ZW0+PHN0cm9uZz5OPC9zdHJvbmc+PC9lbT4uPC9wPgoKPHAgY2xhc3M9"pst">Input
The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.
Output
For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.
Sample Input
4 2 4 5 231
Sample Output
1 2 5 2 4 13 3 5 21 4 231 32549
Source
Greater New York 2006在第一象限，从点（0,0)到点(x,y)画一条线段，如果这条线段不经过其它整数点坐标，那么称作点（x，y）是可见的。给你n，让你计算在0<=x<=n和0<=y<=n的范围内有多少可见点。 当你写出几组点之后，就会发现这些点的横坐标合纵坐标是互素的，因此通过求欧拉函数打表就可以求出。
//392K 0MS
#include
#include
#define N 1007 int sum[N],phi[N]; void getphi() { memset(phi, 0, sizeof (phi));//phi存的就是欧拉函数 sum[1]=1; phi[1] = 1; for (int i = 2; i < N; ++i) { if (!phi[i]) { for (int j = i; j < N; j += i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } sum[i]=sum[i-1]+phi[i]; } } int main() { int cas=1,n,t; getphi(); scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d %d %d\n",cas++,n,sum[n]*2+1); } return 0; }