题目描述
设(x0,y0)是不可见点,那么gcd(x0,y0)一定等于1;
符合题意的连线图是对称的,只考虑y<x部分,结果乘二即可。
样例
输入:
4
2
4
5
231
输出:
1 2 5
2 4 13
3 5 21
4 231 32549
算法
(暴力枚举) $O(n^2)$
blablabla
C++ 代码
const int N=1010;
int n,c[N],a[N];
int res=3;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a; //求最大公约数
}
void niuma()
{
int x,y;
a[1]=res;//从x=2开始枚举
for(x=2;x<=N;x++)
{
for(y=1;y<x;y++)
{
if(gcd(x,y)==1) res+=2;//图是对称的,要乘以2
}
a[x]=res;
}
}
int main()
{
niuma();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
for(int i=1;i<=n;i++)
{
printf("%d %d %d\n",i,c[i],a[c[i]]);
}
return 0;
}