Visible Lattice Points（规律题）【数学规律】

Visible Lattice Points

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9031		Accepted: 5490

Description

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.

Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N.

Input

The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.

Output

For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.

Sample Input

Sample Output

1 2 5
2 4 13
3 5 21
4 231 32549

思路：

问题：从原点出发的射线从x轴开始逆时针旋转，如果射线穿过某点则这个点则该点可以被看到求可以看到的点的个数总和

知道这个题是有规律（找到斜率相同且最先出现的点）直接看看了好久也没找到，最后自己索性把所有要被与原点相连接的点打印出来就可以看出来了

输出如图：

三个值分别表示：

x y k

规律：如果x是奇数（例如x=7）需要满足gcd（x，y）==1的点若是偶数同理

即：x与y互质（佩服同学能直接看出来互质……）

下面是找规律的代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAX=1e6;
struct node{
    double count2;
    LL x;
    LL y;
}num[MAX+5];
struct node1{
    LL x1;
    LL y1;
    double num3;
}edge[MAX+5];
bool cmp(node a,node b)
{
    if(a.count2==b.count2){
        return a.x<b.x;
    }
    else{
        return a.count2<b.count2;
    }
}
bool cmp1(node1 a,node1 b)
{
    if(a.x1!=b.x1){
        return a.x1<b.x1;
    }
    return a.y1<b.y1;
}
int main()
{
    LL count,T,n;
    scanf("%lld",&T);
    for(LL k=1;k<=T;k++){
        scanf("%lld",&n);
        count=0;
        for(LL i=2;i<=n;i++){
            for(LL j=1;j<i;j++){
                num[count].count2=(j*1.0)/(i*1.0);
                num[count].x=i;
                num[count].y=j;
                count++;
            }
        }
        sort(num,num+count,cmp);
        LL count1=0,count3=0;
        for(LL i=0;i<count;i++){
            if(num[i].count2!=num[i-1].count2){
                edge[count3].x1=num[i].x;
                edge[count3].y1=num[i].y;
                edge[count3++].num3=num[i].count2;
               // printf("*%lld %lld %.2lf
",num[i].x,num[i].y,num[i].count2);
                count1++;
            }
        }
        sort(edge,edge+count3,cmp1);
        for(int i=0;i<count3;i++){
            printf("*%lld %lld %.2lf
",edge[i].x1,edge[i].y1,edge[i].num3);
        }
        if(n==1){
            printf("%lld 1 3
",k);
        }
        else{
            LL sum=3;
            sum+=count1*2;
            printf("%lld %lld %lld
",k,n,sum);
        }
    }
    return 0;
}

AC代码：

(找规律接近100行但AC却只是40行左右)

#include<stdio.h>
typedef long long LL;
const int MAX=1e5;
int gcd(int a,int b)
{
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int main()
{
    LL num[MAX+5]={0},T;
    num[1]=1;
    for(int i=2;i<=1000;i++){
        LL count=0;
        if(i%2==0){
            for(int j=1;j<i;j+=2){
                if(gcd(i,j)==1){
                    count++;
                }
            }
        }
        else{
            for(int j=1;j<i;j++){
                if(gcd(i,j)==1){
                    count++;
                }
            }
        }
        num[i]=num[i-1]+count;
    }
    scanf("%lld",&T);
    for(LL k=1;k<=T;k++){
        LL n,sum=0;
        scanf("%lld",&n);
        sum+=(num[n]*2+1);
        printf("%lld %lld %lld
",k,n,sum);
    }
    return 0;
}