10166 관중석

 

모든 각을 저장하면 될 것 같았다. 

 

1이면 360 2면 180 360 이렇게 각이 나오는데 길이가 360인 배열을 만들어두고 관중석이 있는 각을 1로 체크한 뒤 1의 개수만 세면 될 줄 알았다. 하지만 틀렸다.

 

생각해보니 2000까지 수가 들어올텐데 360 / 2000하면 소숫점이 나올테고 실수를 저장하긴 어렵다고 생각됐다. 그래서 그 다음으로 분수 자체를 저장하려고 했다. 

 

4등분 한 수를 저장하려고 하면 1/4 2/4 3/4 4/4를 저장할 수 있는데 여기서 2/4, 4/4를 2로 나누면 1/2, 2/2가 된다. 

 

이렇게 기약분수 꼴로 만들었을 때 그 분수를 저장해두고 중복인지 아닌지 체크해주면 된다. 

 

기약분수는 최대공약수로 나누면 되니깐 gcd함수를 따로 만들었고 분수 저장은 2차원 배열로 만들어 i가 분자 j가 분모를 저장하게 했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int check[2005][2005];

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

int main() {
    int d1, d2;
    scanf("%d %d", &d1, &d2);
    
    int sum = 0;
    for (int i = d1; i <= d2; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            int t = gcd(i, j);
            //printf("%d ", t);
            if (check[j / t][i / t] == 0)
                sum++;
            check[j / t][i / t] = 1;
            // printf("\n");
        }
    }
    
    printf("%d\n", sum);
    
    
    return 0;
}