Demical 객체를 써서 푸는것 말고

분할정복으로 푸는 방법에 대한 접근법을 알려주시면 감사하겠습니다.

onjo0127   9달 전

http://oj.uz/contest/KRIII4PRACTICE/view/1

여기에 푸는 방법이 있네요

onjo0127님 감사합니다.

다만 저것은 A^x의 나머지 연산 값을 구하는것이고, 해당 문제는 모든 값을 온전히 저장해야하는것 아닌지요?

9^100 같이 큰 수를 구해야 할 경우에는나머지 연산이 들어갈 경우 값을 제대로 계산하지 못하는것 아닌것인지..

onjo0127   9달 전

그렇네요... 문제를 제대로 안 읽었네요


그럼 어떻게 해야 되지...

indioindio   9달 전

저는 decimal 대신 BigInteger클래스같은 임의의 크기 정수형으로 계산을 한뒤에, 필요한 소수부만큼 쉬프트 하였는데요
이를 말씀하신 분할정복법에 적용하자면 정수부와 소수부를 나눈 뒤에 a^100 을
a^50을 구한뒤에 (정수부 + 소수부) * (정수부 + 소수부 ) (소수부이지만 자료형은 정수형) 같은 방식으로 계산하면 될 것 같네요.

indioindio님 감사합니다.

결국 BigInteger나 Demical은 필요한것인걸까요..

indioindio   9달 전

찝찝하시다면 BigInteger를 직접 구현하시는 것도 한 가지.. 방법이.. 아닐까 싶네요.

아마 이 문제의 의도도 큰 정수형으로 계산을 한 뒤에 적절히 나눠서 출력하라인 것 같습니다.

koosaga   9달 전

(직접 구현했든 라이브러리를 썼든) BigInteger나 Decimal 같은 것은 무조건 필요합니다.

출력의 정확도가 1000자리 언저리까지 갈수 있기 때문에 프로그래밍 언어의 기본 자료형으로는 구현이 불가능합니다.

여러분 모두 감사합니다!! ^^

댓글을 작성하려면 로그인해야 합니다.