POJ 3090 Visible Lattice Points

Visible Lattice Points

Time Limit: 1000MS Memory Limit: 65536K

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, y) with 0 ≤ x, y ≤ N.

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

题意：

题目要求我们求出有多少个点不在同一个直线上，同时符合 0 ≤ x, y ≤ N.。

思路：

不再同一条直线上就说明k不同，所以也就是说y / x的不同，所以也就是gcd(x, y) = 1这样可以让k最简，而如果不等于1的时候，那么被等于1的时候给覆盖，所以就是求欧拉函数就行了，最后因为x,y的值可以互换，所以就每个欧拉值要乘2，因为还有一个对称轴(1, 1)所在的线，所以前缀和要+1。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1010;
int sum[maxn], phi[maxn], prime[maxn];
bool book[maxn] = {false};
void GetPhi() {
    int cnt = 0;
    phi[1] = 1;
    for (int i = 2; i < maxn; i++) {
        if (!book[i]) {
            phi[i] = i - 1;
            prime[cnt++] = i;
        }
        for (int j = 0; j < maxn && prime[j] * i < maxn; j++) {
            int x = prime[j];
            book[x * i] = true;
            if (i % x == 0) {
                phi[i * x] = phi[i] * x;
                break;
            } else phi[i * x] = phi[i] * phi[x];
        }
    }
    sum[0] = 1;
    for (int i = 1; i < maxn; i++) {
        sum[i] = sum[i - 1] + phi[i] * 2;
    }
}
int main() {
    ios::sync_with_stdio(false);
    GetPhi();
    int t, n;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++) {
        scanf("%d", &n);
        printf("%d %d %d\n", i, n, sum[n]);
    }
    return 0;
}