2^100 구하기와 같은 문제입니다.
방법은 큰 수를 배열로 표시하는 거죠.
예를 들어 123,567,901라는 수를 arr[10]으로 표시할때
천 단위로 끊으면
a[0] = 901
a[1] = 567
a[2] = 123
으로 나타낼 수 있고
만 단위로 끊으면
a[0] = 7901
a[1] = 2356
a[2] = 1
로 표현 가능합니다.
11^100 이 대략 1e104 정도 나오네요
11^9000 이면 1e9360 정도니까 주어진 조건 배열 사이즈 10,000 에선
십 단위로 끊어서 표현해도 되겠네요.
사실 백 단위 이상으로 끊어 표시하게 되면 마지막에 출력할때 끊는 단위에 맞춰서
출력하는 것도 고려해야하는데, (백 단위를 예를 들면 printf("%02d", a[i]); )
십 단위로 하시게 되면 그런 문제는 신경 안쓰셔도 됩니다.
배열을 사용해서 큰 수를 표시하세요.
2^100 구하기와 같은 문제입니다.
방법은 큰 수를 배열로 표시하는 거죠.
예를 들어 123,567,901라는 수를 arr[10]으로 표시할때
천 단위로 끊으면
a[0] = 901
a[1] = 567
a[2] = 123
으로 나타낼 수 있고
만 단위로 끊으면
a[0] = 7901
a[1] = 2356
a[2] = 1
로 표현 가능합니다.
11^100 이 대략 1e104 정도 나오네요
11^9000 이면 1e9360 정도니까 주어진 조건 배열 사이즈 10,000 에선
십 단위로 끊어서 표현해도 되겠네요.
사실 백 단위 이상으로 끊어 표시하게 되면 마지막에 출력할때 끊는 단위에 맞춰서
출력하는 것도 고려해야하는데, (백 단위를 예를 들면 printf("%02d", a[i]); )
십 단위로 하시게 되면 그런 문제는 신경 안쓰셔도 됩니다.
끊어서 표현하는건 할수있는데 문제는 11^9000의
끊어서 표현하는건 할수있는데
문제는 11^9000의 대략적인 값이아닌 1의단위까지 정확히구해야합니다..
가령 2^10승이라하면 a[0]~a[9995]=0 a[9996]=1 a[9997]=0 a[9998]=2 a[9999]=4 이런식으로 정확하게 구해야하는데
addnull님이 설명해주신거론 어떻게해야할지 모르겠네요 ㅜㅜ
숫자를 배열로 끊어서 표현한다는건
숫자를 배열로 끊어서 표현한다는건
11^1, 11^2, 11^3 ... 11^9000 을 반복적으로 구하되,
결과인 11, 121, 1331 ... 을 배열로 끊어서 표현한다는 것을 말합니다.
예를 들어 11^3 = 1331을 구했을땐,
a[0] = 1
a[1] = 3
a[2] = 3
a[3] = 1
라고 저장되어있겠죠.
그럼 여기서 11^4를 구하는건
a[0] *= 11;
a[1] *= 11;
a[2] *= 11;
a[3] *= 11;
해야하는데, 각 배열 element는 0~9 까지 숫자만 표현해야하므로 (십 단위로 끊어서 표현했으니까요.)
올림수(carry)를 고려해야죠.
가장 작은 단위 a[0] *= 11 과 그 다음 단위 a[1]을 계산하는걸 예를 들면
tmp = a[0] * 11;
carry = tmp / 10;
a[0] = tmp % 10;
tmp = a[1] * 11 + carry;
carry = tmp / 10;
a[1] = tmp % 10;
입니다.
a[2] 는 a[1] 구할때 구해진 carry를 포함해서 계산하는 식으로 반복해나가면 됩니다.
제 설명이 어려우시다면, 아래 링크에서 FlopCoder님의 답변을 참고하세요.
http://stackoverflow.com/questions/9554944/2-pow-x-using-large-integers
modular exponentiation
modular exponentiation 과 같은 기법을 궁금해하시는거 아닐까요
나머지는 문제될건 없어보이네요
자기실력이 좋다고 느껴지는건 공부를 안하고 있다는 신호.
밑이 11이라서 간단한 접근이 가능할 것
밑이 11이라서 간단한 접근이 가능할 것 같습니다.
char a[10000] = {0,};
a[0] = 1;
a[1] = 1;
반복하기를...
{
a[9999] += a[9998];
a[9998] += a[9997];
...
a[2] += a[1];
a[1] += a[0];
a[0], a[1], ... a[9998] 순으로 10을 넘는지 테스트해서
자리올림 처리
}
a[9999], a[9998], ..., a[1], a[0] 순으로 결과출력..
스쳐지나가는 생각을 캐치한것인데, 결과가 나오려나 모르겠네요.
댓글 달기