学步园

       欧拉函数题。题意：一个在第一象限的格点（x，y），x和y可以为0且x和y必须是整数。如果一条线段从原点到这个格点不经过其他格点，那么我们称这个格点是有价值的。现在给你范围n，请你求x和y不大于n的情况下有多少有价值的格点。

       我的解题思路：首先，如果从原点到（x，y）这个格点的线段经过其他格点，假设这个格点为（a，b），那么容易知道x / a = y / b，假设等于c，可以断定c必定不等于1，否则格点（a，b）就是格点（x，y），也就是说这个线段不经过其他格点，这和假设相反。因此，可以知道，如果x和y的最大公约数为1，也就是说x与y互素，那么这个格点（x，y）就是有价值的格点。问题就转化成求欧拉函数了，我们可以得到这样的信息：横坐标为x且纵坐标不大于x的有价值格点个数为phi(x)，纵坐标也一样。因此我们把phi表存储成前缀和的形式，那么n范围内的有价值格点就是2×phi[n]，这和样例答案并不一样，我们需要考虑一下边界情况，当横坐标为1且纵坐标不大于1的有价值格点是（1，1），纵坐标为1时也是这样，因此有价值格点（1，1）算了两次，需要把2×phi[n]减去1。另外，因为x和y可以等于0，所以（1，0）和（0，1）也是有价值的格点，我们需要把这两个点算上，再加上2，最后得到的答案就是2×phi[n]-1，注意这个phi数组要存储为前缀和数组。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1003;

int phi[N];
int n;

void InitRead();

void DataProcess();

void GetPhi(int maxn);

int main()
{
    int t;
    scanf("%d", &t);
    InitRead();
    while (t--)
    {
        DataProcess();
    }
    return 0;
}

void InitRead()
{
    memset(phi, 0, sizeof(phi));
    phi[1] = 1;
    GetPhi(N);
    for (int i=2; i<N; ++i) phi[i] += phi[i-1]; //存储成前缀和数组
    return;
}

void DataProcess()
{
    static int tn = 1;
    scanf("%d", &n);
    printf("%d %d %d\n", tn++, n, phi[n] * 2 + 1);
    return;
}

void GetPhi(int maxn)
{
    for (int i=2; i<maxn; ++i)
    {
        if (!phi[i])
        {
            for (int j=i; j<maxn; j+=i)
            {
                if (!phi[j]) phi[j] = j;
                phi[j] -= phi[j] / i;
            }
        }
    }
    return;
}