[2942번] 퍼거슨과 사과

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최대 공약수

이 문제는 결국 두 수 사이의 최대 공약수를 구한 후 그 최대 공약수까지 for문을 돌려 나누어떨어지는 수에 대해 체크해주면 된다.

좀더 좋은 방법이 있는 것으로 알고있는데 그 방법에 대해서는 다음 링크를 참고해보자. 

https://www.acmicpc.net/board/view/682

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cmath> #include <map>   using namespace std;   int gcd(int a, int b) {     return !b ? a : gcd(b, a%b); }   int main() {     int a, b;     cin >> a >> b;       int g = gcd(min(a, b), max(a, b));          for(int i = 1; i <= g; i++)         if(a % i == 0 && b % i == 0)             printf("%d %d %d\n", i, a / i, b / i);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus