题目描述

ZPS经过长期的努力争取，终于成为了0901班的领操员，他要带领0901班参加广播操比赛。现在0901班的队伍可以看作是一个n*n的点阵，每个人都站在格点上。现在作为领操员的ZPS站(0,0)点，他想知道如果0901班的队伍站齐了，他能看到多少个人的脸（假设每个人的身高相同，体积相同）。

思路

对于一个点(x,y)来说，如果i，j互质，那么这个点就是可以被看到的，所以我们就可以用欧拉函数来求解这题，然后用线性筛的方法就不会T了

#include 
#define maxn 100001
#define LL long long
LL phi[maxn];
int main()
{
    LL n;
    scanf("%lld", &n);
    if (n == 1)
    {
        printf("0\n");
        return 0;
    }
    n--;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (phi[i] == 0)
        {
            int j = i;
            while (j <= n)
            {
                if (phi[j] == 0) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
                j += i;
            }
        }
    }       
    LL ans = 0;
    for (int i = 1; i <= n; i++)
        ans += phi[i];
    printf("%lld\n", ans * 2 + 1);
}

#include 
#define maxn 100001
#define LL long long
int prime[maxn];
bool notPrime[maxn];
LL phi[maxn];
int main()
{
    LL n;
    scanf("%lld", &n);
    if (n == 1)
    {
        printf("0\n");
        return 0;
    }
    phi[1] = 1;
    int tot = 0;
    for (int i = 2; i <= n; i++)    
    {
        if (!notPrime[i])
        {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * prime[j] < n; j++)
        {
            notPrime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for (int i = 2; i < n; i++)
        phi[i] += phi[i - 1];
    printf("%lld\n", phi[n - 1] * 2 + 1);
}

]]>