[정올] 2797 / 관중석

각을 분수로 표현해서 구한다.

r = 3일때 1번째는 0/3, 2번 째는 1/3, 3번째는 2/3으로 만든다.

r = 6일때 2번째는 2/6, 그러니까 1/3 인데 r = 3 일때 1/3이 존재했다는걸 알 수 있다.

이런식으로 [몇번 째 인지] - 1 / [r] 을 기약분수로 만들어 가려지는지 확인할 수 있다.

기약분수로 만들때는 gcd를 사용하자.

 

#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
#include <map>
#include <set>
#include <math.h>
#include <numeric>
#include <cassert>
#include <stack>
#include <cstring>
#include <unordered_set>
using namespace std;
#define interface struct
#define zx3f 1061109567
#define itn int
#define _DEBUG_ 0
#define dout     \
    if (_DEBUG_) \
    cout
typedef long long ll;
typedef unsigned long ull;
typedef pair<int, int> pii;
typedef signed char i8;
typedef short i16;
typedef int i32;
typedef long long i64;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template <typename T>
class CVector
{
public:
    vector<T> vec;

    CVector()
    {
    }
    CVector(int size)
    {
        vec.reserve(size);
    }
    CVector(size_t size)
    {
        vec.reserve(size);
    }

    void push(T v)
    {
        vec.push_back(v);
    }

    void push_back(T v)
    {
        vec.push_back(v);
    }

    void remove_duplicate()
    {
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
    }

    void fast_pop()
    {
        vec.pop_back();
    }

    void clear()
    {
        vec.clear();
    }

    T &at(size_t idx)
    {
        if (idx < 0)
        {
            idx = vec.size() + idx;
        }
        return this->vec[idx];
    }

    T pop()
    {
        T ld = vec.back();
        vec.pop_back();
        return ld;
    }

    T pop_back()
    {
        T ld = vec.back();
        vec.pop_back();
        return ld;
    }

    T back()
    {
        return vec.back();
    }

    T front()
    {
        return vec.front();
    }

    T &operator[](size_t idx)
    {
        return this->at(idx);
    }

    size_t size()
    {
        return vec.size();
    }

    size_t lastIndex()
    {
        return this->size() - 1;
    }

    bool empty()
    {
        return vec.empty();
    }

    auto begin()
    {
        return vec.begin();
    }

    auto end()
    {
        return vec.end();
    }

    auto capacity()
    {
        return vec.capacity();
    }
};

int d1, d2;

bool used[2005][2005];

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

ull getCount(int r)
{
    ull ans = 0;
    for (int i = 0; i < r; i++)
    {
        int gc = gcd(i, r);
        int a = i / gc;
        int b = r / gc;
        if (used[a][b])
            continue;
        used[a][b] = 1;
        ans++;
    }
    return ans;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> d1 >> d2;
    unsigned long long cnt = 0;
    for (int i = d1; i <= d2; i++)
    {
        cnt += getCount(i);
    }
    cout << cnt;
}