POJ3090 Visible Lattice Points（欧拉函数）

• 题目大意：给你一个n*n的网格，任意一点和(0,0)连线，可以组成一条直线，前面的点可以挡住后面的点，问你能看到的点到底有多少个
• 思路分析：题目实际上就是问在这个网格上有多少种不同的斜率，边上的两点我们先不管，然后将整个正方形分成上三角和下三角两部分，
  由对称性，两边可以看到的点的数目肯定一样多，以下三角为例进行研究，我们会发现，对于所有能看到的点，他们有着一个共同的特征，
  那就是gcd(x,y）=1,若不为1，则他前面肯定有一个点挡住了这个点，那么本题就转变成了一个求欧拉函数和的简单题目，注意不要将分界线
  上的点加，记t=phi[1]+phi[2]+…….+phi[n]，则ans=(t-1)*2+1+2=2*t+1

//孔乙己你又去偷代码了？

#include<iostream>
#include<cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=1500;
int prime[maxn];
int phi[maxn];
bool check[maxn];
int tot;
void make_prime()
{
    phi[1]=1;
    memset(check,true,sizeof(check));
    tot=0;
    for(int i=2;i<=maxn;i++)
    {
        if(check[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot&&i*prime[j]<=maxn;j++)
        {
            check[i*prime[j]]=false;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int kase;
int main()
{
    int T;
     make_prime();
    scanf("%d",&T);
    kase=0;
    ll num;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=phi[i];
        }
        printf("%d %d %lld\n",++kase,n,ans*2+1);
    }
}