백준 10166 관중석

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

모든 좌석은 분수꼴로 표현할 수 있습니다. 해당 분수를 기약분수로 나타냈을 때 겹치는 분수가 있다면 더 이상 세지 않습니다. 배열을 하나 잡고 방문 여부를 확인해주면 됩니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=2005;
int vst[SZ][SZ];
int gcd(int x, int y){
	return x%y? gcd(y,x%y):y;
}
int main(void){
	int x,y; cin>>x>>y;
	int ans=0;
	for(int i=x;i<=y;i++){
		for(int j=1;j<=i;j++){
			int g=gcd(i,j);
			if(vst[i/g][j/g]==0){
				vst[i/g][j/g]=1;
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}