문제
https://www.acmicpc.net/problem/2725
문제해설
정사각형의 좌표 n이 주어지면 원점에서 자연수로 된 좌표가 몇개 보이는지 찾는 문제다.
다만 기울기가 같아 겹치는 좌표는 제외한다.
문제풀이
풀이의 아이디어를 생각해내는게 참 어려운 문제같다.
생각만 해낸다면 구현은 어렵지 않다.
일단 기울기로 접근해보자 기울기가 같은 점들은 겹치므로 하나만 카운트된다.
그렇다면 유일한 기울기를 가진 점들을 체크해주면 된다.
그걸 가장 심플하게 구할 수 있는 방법은 최대 공약수를 구하면 된다.
최대공약수가 1일 때에만 카운트를 증가시켜주면 되는 것이다.
그리고 테스트케이스가 최대 1000개까지 들어올 수 있다.
1000개를 계속 구한다면 시간초과가 나기 때문에 배열에 정답을 저장해놓고 출력만 한다.
구한 횟수에 2를 곱하는데 그건 양수의 기울기만 구하기 때문이다.
전체코드
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
#include<iostream>
using namespace std;
int res[1001];
int gcd(int a, int b) {
int t;
while (b) {
t = a % b;
a = b;
b = t;
}
return a;
}
int main() {
int c;
scanf("%d", &c);
res[1] = 3;
for (int i = 2; i <= 1000; i++) {
int cnt = 0;
for (int j = 1; j < i; j++) {
if (gcd(i, j) == 1)
cnt++;
}
res[i] = res[i - 1] + 2 * cnt;
}
while (c--) {
int n;
scanf("%d", &n);
printf("%d\n", res[n]);
}
return 0;
}