poj 3090 Visible Lattice Points 法利系列||通过计-白红宇

poj 3090 Visible Lattice Points 法利系列||通过计

阅读量：6853 次

发布时间：2019-06-26

本文共 1655 字，大约阅读时间需要 5 分钟。

因为图像关于对角线对称。所以我们仅仅看下三角区域。

将x轴看做分母，被圈的点看成分子

依次是{1/2},{1/3,1/2},{1/4,3/4},{1/5,2/5,3/5,4/5}

写成前缀和的形式就是 {1/2},{

1/2,1/3,2/3},{

1/2,1/3,2/3,1/4,3/4},{

1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5}

发现。这就是一个法雷级数，即第k项添加的数就是phi[k]。

最后的答案*2+(0,1)+(1,0),(1,1)三个点就好了

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 1009int phi[N];int Farey[N]={0,0,1};void init(){    int i, j;    for(i = 1; i < N; i++)        phi[i] = i;    for(i = 2; i < N; i++)        if(i == phi[i])            for(j = i; j < N; j += i)                phi[j] = (phi[j] / i) * (i - 1);}int main(){    init();    for(int i=3;i

没有发现这个规律的话，也能够递推打表做，类似矩阵和的存储，用gcd推断当前点是否被之前的点挡住。

#include 
     
      #include 
      
       #include 
       
        #include
        
         #include
         
          using namespace std;int mp[1005][1005];bool vis[1005][1005];int gcd(int a,int b) {return a%b==0?b:gcd(b,a%b);}int a[1005][1005];int main(){    memset(vis,0,sizeof(vis));    int ans=0;    for(int i=1;i<=1000;i++)    {        for(int j=1;j<=1000;j++)        {            int gg=gcd(i,j);            if(vis[i/gg][j/gg])            {                a[i][j]+=a[i-1][j]+a[i][j-1];                a[i][j]-=a[i-1][j-1];                continue;            }            else            {                vis[i][j]=1;                a[i][j]+=a[i-1][j]+a[i][j-1]+1;                a[i][j]-=a[i-1][j-1];            }        }    }    int n;    int ca=1;    int cas;    scanf("%d",&cas);    while(cas--)    {        scanf("%d",&n);        printf("%d %d %d\n",ca++,n,a[n][n]+2);    }    return 0;}