因为图像关于对角线对称。所以我们仅仅看下三角区域。
将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 <iostream>
#include <cstdio>
#include <cmath>
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<N;i++)
{
Farey[i]=Farey[i-1]+phi[i];
}
int cas,n,ca=1;
scanf("%d",&cas);
while(cas--)
{
scanf("%d", &n);
printf("%d %d %d\n",ca++,n,Farey[n]*2+3);
}
return 0;
}
没有发现这个规律的话，也能够递推打表做，类似矩阵和的存储，用gcd推断当前点是否被之前的点挡住。
#include <iostream>
#include <cstdio>
#include <cmath>
#include<cstring>
#include<cstdlib>
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;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。