[백준] 13728 - 행렬식과 GCD

[문제]

https://www.acmicpc.net/problem/13728

[풀이]

행렬식과 여인자를 통해 $D(k)$를 확인한다.
$k\geq 3$ 일 때, $D(k)=D(k-1)+D(k-2)$ 를 만족한다.

$k\cdot k$ 행렬 $M$에 대하여 $M_{11}\cdot D(k-1) - M_{12}\cdot (-D(k-2)+0)$ 이므로 정리하면 위의 식을 얻을 수 있다.

한편, $D(1)=1, D(2)=2$ 이므로 피보나치 수열의 형태임을 알 수 있다.

문제의 출력을 보면 gcd값을 모두 더해야하는데, $N$이 매우 크므로 일일히 gcd를 구할 수는 없다.
또한, 모듈러 연산의 gcd값이 원하는 값과 일치한다는 보장이 없다.
피보나치 수열 gcd에 관해 아래 링크를 통해 알게 되었다.

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciMatrix.shtml#nice

결론은, $gcd(f_i,f_j)=f_{gcd(i,j)}$이다.
피보나치 수열은 1 1 2 3 5 .. 이지만
$D(k)$의 값은 1 2 3 5 8 .. 이므로 이 차이를 고려했다.

[코드]

N=int(input())
if N == 1: print(1);exit()
def gcd(a,b):
    if(b>a): a,b=b,a
    while True:
        r = a%b
        if r == 0: return b
        a = b
        b = r
MOD=10**9+7
D=[1]*(N+1)
D[2]=2
for i in range(3, N+1):
    D[i]=(D[i-1]+D[i-2])%MOD
S=0
for i in range(1,N+1):
    S +=D[gcd(i+1,N+1)-1]
    S %= MOD
print(S)