bgy7005   6년 전

왜 틀렸다고 나오는 걸까요?

chogahui05   6년 전

나눗셈 때문입니다.

result가 100000008이였습니다. 이걸 100000007로 나눈 나머지는 1이였겠죠.


원래 result를 토대로 4/2를 해 봅시다.

1000000008 * 1/2 = 500000004


1000000008을 1000000007로 나눈 나머지는 1입니다.

1*1/2는 얼마일까요?

chogahui05   6년 전

전체적인 접근 방향은 맞습니다.

꽤 빠른 시간 내에 풀기 위해서는 여러 가지 수학 지식이 필요하고요.

무슨 인버스니 역원이니.. 솔직히 머리 아파집니다. 이 문제 AC수도 많은데 무난하게 풀어봅시다.


제 방법은

소인수 분해를 하는 것인데요. 구현하시는 분에 따라 방법이 달라지실 수 있겠습니다만.. 제 방법은요.


(1) 소수 목록들을 다 구하신 후에

O(nlog(logn))


(2) 포함 배제의 원리 + 여집합을 이용해서 소인수 분해를 해 보세요.

포함 배제를 이용하시면 소수 m이 들어왔을 때

한 Query당 O(logmn)에 처리 가능합니다.

이건 시간복잡도를 계산 못 하겠는데요. 소수들이 전체 수에 비해 꽤 작고 나누는 수가 커질수록

검사해야 하는 횟수가 많이 줄어들기 때문에.. (1)과 엇비슷하거나 줄지 않을까 싶네요.


어짜피 소인수 분해는

k = a^n * b^m * ... (단 a라던지 b라던지 밑에 있는 것은 모두 소수)

이런 식으로 되니까요. 

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