BOJ 13817, Everlasting...?
ProblemSolving ·단순 구현문제입니다. 소인수 분해한 값을 이용하는 문제입니다.
풀이
첫 번째, a와 b를 소인수 분해하여 그 수들을 각 an, bn 배열에 체크해줍니다.
두 번째, 가장 큰 소인수에 나머지 소인수들을 빼줍니다.
세 번째, 2번의 값을 서로 비교해서 출력해줍니다.
#include<stdio.h>
int a, b, Ma, Mb;
int main()
{
while (1)
{
int an[1000001] = { 0, };
int bn[1000001] = { 0, };
scanf("%d %d", &a, &b);
if (a == 0 && b == 0)
break;
int n = 2;
while (a>1)
{
if (a%n == 0)
{
an[n] = 1;
a /= n;
}
else
n++;
}
Ma = n;
n = 2;
while (b>1)
{
if (b%n == 0)
{
bn[n] = 1;
b /= n;
}
else
n++;
}
Mb = n;
int j = Ma;
for (int i = 1; i < j; i++)
if (an[i] == 1)
Ma -= i;
j = Mb;
for (int i = 1; i < j; i++)
if (bn[i] == 1)
Mb -= i;
if (Ma > Mb)
printf("a\n");
else
printf("b\n");
}
return 0;
}