POJ 3090 Visible Lattice Points 欧拉函数

题意：在坐标系中，从横纵坐标 0 ≤ x, y ≤
N中的点中选择点，而且这些点与（0,0）的连点不经过其它的点。

思路：显而易见，x与y仅仅有互质的情况下才会发生（0,0）与（x,y）交点不经过其它的点的情况，对于x,y等于N时，能够选择的点均为小于等于N而且与N互质的数，共Euler(N)个，而且不重叠。所以能够得到递推公式aa[i]=aa[i]+2*Euler(N)。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <map>

#include <cstdlib>

#include <queue>

#include <stack>

#include <vector>

#include <ctype.h>

#include <algorithm>

#include <string>

#include <set>

#define PI acos(-1.0)

#define maxn 10005

#define INF 0x7fffffff

#define eps 1e-8

typedef long long LL;

typedef unsigned long long ULL;

using namespace std;

int aa[1005];

int Euler(int tot)

{

    int num=tot;

    for(int i=2; i<=tot; i++)

    {

        if(tot%i==0)

            num=num/i*(i-1);

        while(tot%i==0)

            tot/=i;

    }

    return num;

}

void init()

{

    aa[0]=0;

    aa[1]=3;

    for(int i=2; i<=1000; i++)

        aa[i]=aa[i-1]+Euler(i)*2;

}

int main()

{

    int T;

    scanf("%d",&T);

    init();

    for(int ii=1; ii<=T; ii++)

    {

        int tot;

        scanf("%d",&tot);

        printf("%d %d %d\n",ii,tot,aa[tot]);

    }

    return 0;

}

秒客网

POJ 3090 Visible Lattice Points 欧拉函数

相关文章