BOJ 1850 최대공약수

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

---

입력받은 A와 B의 최대공약수만큼 1이 반복된다는 것만 알면 쉽게 풀 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include<stdio.h> #define SWAP(i,j) i^=j^=i^=j #define FOR(i,j) for(int i=1;i<=j;i++) int main() { long long int A, B; scanf("%lld %lld", &A, &B); for (;;) { if (B > A) SWAP(A, B); if (!(A%B)) { FOR(i, B) printf("1"); break; } else A %= B; } return 0; }