[1850번] 최대공약수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 규칙

2. gcd :: http://www.crocus.co.kr/578

규칙만 찾으면 끝이다.

입력되는 a, b의 두 gcd의 값이 결국 출력해야할 1의 개수이다.

소스 코드 : 

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

#include <iostream> #include <cstdio>   typedef long long ll;   ll gcd(ll a, ll b) { return !b ? a : gcd(b, a%b); }   using namespace std;   int main() {     ll a, b;       scanf("%lld %lld", &a, &b);       ll len = gcd(a, b);       for (ll i = 0; i < len; i++)         printf("1");       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus