나눗셈 때문입니다.
result가 100000008이였습니다. 이걸 100000007로 나눈 나머지는 1이였겠죠.
원래 result를 토대로 4/2를 해 봅시다.
1000000008 * 1/2 = 500000004
1000000008을 1000000007로 나눈 나머지는 1입니다.
1*1/2는 얼마일까요?
11401번 - 이항 계수 3
나눗셈 때문입니다.
result가 100000008이였습니다. 이걸 100000007로 나눈 나머지는 1이였겠죠.
원래 result를 토대로 4/2를 해 봅시다.
1000000008 * 1/2 = 500000004
1000000008을 1000000007로 나눈 나머지는 1입니다.
1*1/2는 얼마일까요?
전체적인 접근 방향은 맞습니다.
꽤 빠른 시간 내에 풀기 위해서는 여러 가지 수학 지식이 필요하고요.
무슨 인버스니 역원이니.. 솔직히 머리 아파집니다. 이 문제 AC수도 많은데 무난하게 풀어봅시다.
제 방법은
소인수 분해를 하는 것인데요. 구현하시는 분에 따라 방법이 달라지실 수 있겠습니다만.. 제 방법은요.
(1) 소수 목록들을 다 구하신 후에
O(nlog(logn))
(2) 포함 배제의 원리 + 여집합을 이용해서 소인수 분해를 해 보세요.
포함 배제를 이용하시면 소수 m이 들어왔을 때
한 Query당 O(logmn)에 처리 가능합니다.
이건 시간복잡도를 계산 못 하겠는데요. 소수들이 전체 수에 비해 꽤 작고 나누는 수가 커질수록
검사해야 하는 횟수가 많이 줄어들기 때문에.. (1)과 엇비슷하거나 줄지 않을까 싶네요.
어짜피 소인수 분해는
k = a^n * b^m * ... (단 a라던지 b라던지 밑에 있는 것은 모두 소수)
이런 식으로 되니까요.
댓글을 작성하려면 로그인해야 합니다.
bgy7005 6년 전
왜 틀렸다고 나오는 걸까요?