[C] 백준 1850

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

1850번: 최대공약수

 

입력되는 수는 2^63보다 작은 자연수이므로 long long 데이터 타입을 사용한다.

 

모든 자리가 1로 이루어지기 때문에 A와 B를 이루는 1의 개수의 최대공약수를 구하고

그 최대공약수 만큼 1을 출력하면 A와 B의 최대공약수를 출력할 수 있다.

 

최대공약수는 유클리드 알고리즘을 이용하여 구했다. 

 

#include <stdio.h>

long long func(long long A, long long B)
{
	if (B == 0)
		return A;
	func(B, A % B);
}

int main()
{
	long long A, B, C; // long long의 범위 -2^63 ~ 2^63-1

	scanf("%lld %lld", &A, &B);
	C = func(A, B);

	for (int i = 0; i < C; i++)
	{
		printf("1");
	}

	return 0;
}