首页 > 代码库 > POJ 3090 Visible Lattice Points 欧拉函数

POJ 3090 Visible Lattice Points 欧拉函数

链接:http://poj.org/problem?id=3090

题意:在坐标系中,从横纵坐标 0 ≤ xy ≤ 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;
}