11월 5주차 코드리뷰

11월 5주차 코드리뷰

문제 관중석

이 문제를 접근하기 위해서는 최대 공약수를 이용해야합니다.

최대 공약수를 알기 위해서 

유클리드 호제법을 이용하면

함수하나로 최대 공약수를 찾을 수 있습니다

(http://thrillfighter.tistory.com/68)

코드

#include 
using namespace std;
bool check[2002][2002];

int gcd(int a,int b)
{
   if(b==0)
   {
      return a;
   }
   return gcd(b,a%b);
}
d
int main() {
   int gg,i,j,d1,d2,sum=0;
   scanf("%d %d",&d1,&d2);
   
   for(i=d1;i<=d2;i++)
   {
      sum+=i;
      for(j=1;j<=i;j++)
      {
         gg=gcd(i,j);
         if(check[i/gg][j/gg])
         {
            sum--;
         }
         else
         {
            check[i/gg][j/gg]=true;
         }
      }
   }
   
   return 0;
}