poj 3090 Visible Lattice Points 法雷级数||打表 - c++编程基础

vcfP37bUs8ajrMv50tTO0sPH1ru/tM/CyP29x8f40/Kho72reNbhv7TX9rfWxLijrLG7yKa1xLXjv7SzybfW19M8L3A+CjxwPtLAtM7Kx3sxLzJ9LHsxLzMsMS8yfSx7MS80LDMvNH0sezEvNSwyLzUsMy81LDQvNX08L3A+CjxwPtC0s8nHsNe6us21xNDOyr2+zcrHIHsxLzJ9LHsxLzIsMS8zLDIvM30sezEvMiwxLzMsMS8zLDEvNCwzLzR9LHsxLzIsMS8zLDEvMywxLzQsMy80LDEvNSwyLzUsMy81LDQvNX08L3A+CjxwPreiz9ajrNXivs3Kx9K7uPa3qMDXvLbK/aOsvLS12mvP7tT2vNO1xMr9vs3Kx3BoaVtrXaGj1+6687XEtPCwuCoyJiM0MzsoMCwxKSYjNDM7KDEsMCksKDEsMSnI/bj2teO+zbrDwcs8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include #include #include using namespace std; #define N 1009 int 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; }