시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 454 | 193 | 143 | 41.329% |
다음과 같은 원소를 갖는 크기가 N×N인 행렬이 있다.
예를 들어, 크기 N = 4인 경우 M은 다음과 같다.
1 1 0 0 -1 1 1 0 0 -1 1 1 0 0 -1 1
D(k)를 크기가 k×k인 행렬 M의 행렬식(Determinant)이라고 하자. N이 주어졌을 때, S = Σgcd(D(i), D(N)) (1 ≤ i ≤ N) 을 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 105)
S를 109+7로 나눈 나머지를 출력한다.
1
1
2
3
3
5
4
8
5
13