jhko00   7년 전

처음에 정직하게 b번 반복문을 돌렸더니 시간초과가 떠서 

루트b를 이용하여 시간을 줄이는 방식으로 풀었습니다

a의 루트b 승을 루트b 번만큼 곱하고 남은 b-루트b^2만큼 곱해주면 

예제 및 다른 수를 넣어봐도 값은 이상 없이 나오는 것 같습니다

코드에 주석으로도 적어놨지만 b가 2147483647보다 작거나 같으므로 

반복문이 돌아가는 최대 한도는 d+d+2d(d=루트b) 18만번 정도 입니다

시간 초과는 나지 않는것같고 수를 곱할때마다 바로 c로 나머지를 구해주기 때문에

a나 t가 아무리 커도 c보다 작고 c의 값이 2147483647(2^31-1)이기 때문에 long long int(2^63-1)의 범위 안에

다 포함되서 오버플로우도 안난다고 생각합니다

어느 부분에서 오류가 있는지 봐주시면 감사드립니다

gunwookim   7년 전

long long int 는 처음보네요;;

원래 long long 아닌가요?

jhko00   7년 전

int가 생략가능한것이고 long long int 하고 long long 은 같은 타입으로 알고 있어요

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