시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.5 초 (추가 시간 없음) | 512 MB | 281 | 65 | 25 | 11.161% |
Möbius 함수 $\mu(n)$은 정수론에서 다루는 중요한 multiplicative function 중 하나다.
주어진 양의 정수 $N, L, K$에 대하여, 다음 값을 계산해보자. 값이 커지므로, $10^9+7$로 나눈 나머지를 출력한다.
\begin{equation*}
\displaystyle \sum_{d=1}^N \mu(L \cdot d) \left \lfloor \frac{N}{d} \right \rfloor^K
\end{equation*}
입력은 한 줄에 주어지며, 양의 정수 $N$, $L$, $K$가 순서대로 주어진다.
입력은 $1 \le N \le 10^9$, $1 \le L \le 10^{15}$, $1 \le K \le 10^9$를 만족한다.
$\displaystyle \sum_{d=1}^N \mu(L \cdot d) \left \lfloor \frac{N}{d} \right \rfloor^K$의 값을 $10^9+7$로 나눈 나머지를 출력한다.
100 1 1
1
100 30 10
44609703
100 4 100
0