백준 2725 보이는 점의 개수:: 들짐승

<링크>

https://www.acmicpc.net/problem/2725

<풀이>

한번 나왔던 기울기에 속하는 좌표는 다시는 보일수없다
x/y 가 기울기이다. 

예를 들면 x가 2, y가 8일때 기울기는 2/8이 되는데 이는 이미 1/4에서 나왔기 때문에 보일수없다. 
x가 3, y가 5일때는 같은 기울기가 나왔을 수 없기 때문에 보인다. 


정리하면 
1/y 
2/y 
... 
y/y 
중에서 좌표끼리 분수를 만들고 약분되면 그 좌표는 보일 수가 없다.  
이전에 이미 같은 기울기가 나왔다는 뜻이기 때문이다. 
따라서 분모와 분자의 최대공약수가 1일때만 더해나가면된다.

<소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include<stdio.h> int ans[1001] = { 0,2 }; int gcd(int, int); int main() {     for (int i = 2; i <= 1000; ++i)     {         int n = 0;         for (int j = 1; j <= i; ++j)         {             if (gcd(i, j) == 1)                 ++n;         }         ans[i] = ans[i - 1] + n;     }     int T;     scanf("%d", &T);     while (T--)     {         int N;         scanf("%d", &N);         printf("%d\n", ans[N] * 2 - 1);     } } int gcd(int a, int b) {     while (a%b != 0)     {         int tmp = b;         b = a % b;         a = tmp;     }     return b; } Colored by Color Scripter

cs