[BOJ 10438] 페리 수열의 합

페리 수열 $F_{n}$은 0부터 1까지 분모가 $n$이하인 모든 기약분수들을 오름차순으로 배열한 수열이다.

예를 들어 $n=3$ 이라면 수열은 다음과 같다.

$\frac{0}{1}\ \frac{1}{3}\ \frac{1}{2}\ \frac{2}{3}\ \frac{1}{1}$

• 페리 수열은 이전 수열에 새로운 기약분수가 추가되며 수열이 만들어진다.
• 페리 수열의 $a$번째 항을 $\frac{h_1}{k_1}$, $a+2$번째 항을 $\frac{h_2}{k_2}$, $a+1$번째 항을 $\frac{h_3}{k_3}$이라 하면 $h_{3}=h_{1}+h_{2}$, $k_{3}=k_{1}+k_{2}$ 이다.

이 성질을 이용해 이 다음 페리 수열에 등장할 분수를 알 수 있다.

• 페리 수열의 크기를 $|F_{n}|$이라 하면 $|F_{n+1}|=|F_{n}|+\phi(n+1)$이다.

$n$이 증가할 때마다 다음 항에 몇 개의 항이 추가되는지 알 수 있다. 페리 수열의 정의를 보면 '분모가 $n$이하인 모든 기약분수'가 눈에 띤다. $n$번째 페리 수열에 분모가 $n+1$인 기약분수들이 추가되었다고 보면 된다. 그럼 그 기약분수의 개수는 $n+1$과 서로소인 $n+1$이하의 자연수의 개수와 동일하다. 즉 $\phi(n+1)$이다. 

• 페리 수열의 분모는 중앙에 대해 대칭이다.

그 이유는 단순한데 $n=2$에서 보자.

$F_{n}=\frac{0}{1}\ \frac{1}{2}\ \frac{1}{1}$

$n=2$에서 대칭임을 확인할 수 있는데 새로운 기약분수가 생기는 위치 역시 중앙 대칭임을 알 수 있다. 그럼 이 다음 페리 수열 역시 중앙 대칭이다. 

 

서론이 길었다! 문제에서 요구하는 것은 페리 수열의 분모의 비의 합이다.

예를 들어 페리 수열의 일부분의 분모가 $a$, $k_{1}$, $k_{2}$, $b$라고 하자.(이 부분은 왼쪽이라고 하자.) 중앙 대칭인 성질에 의해 $\frac{1}{2}$의 반대쪽 분모는 $b$, $k_{2}$, $k_{1}$, $a$이다. 이때 이 일부분에 대한 문제의 답을 구해보자.

왼쪽의 합은 $\frac{a}{k_{1}}+\frac{k_{1}}{k_{2}}+\frac{k_{2}}{b}$

오른쪽의 합은 $\frac{b}{k_{2}}+\frac{k_{2}}{k_{1}}+\frac{k_{1}}{a}$

전체 합은 $\frac{a+k_{2}}{k_{1}}+\frac{b+k_{1}}{k_{2}}+\frac{k_{1}}{a}+\frac{k_{2}}{b}$

이제 $k_{1}$과 $k_{2}$사이에 우연히 분모가 $k_{1}+k_{2}$인 기약분수가 생겼다고 해보자. 그럼 원래의 수열은 다음과 같이 바뀐다.

$a$, $k_{1}$, $k_{1}+k_{2}$, $k_{2}$, $b$

이때 합을 다시 구해보자.

왼쪽의 합은 $\frac{a}{k_{1}}+\frac{k_{1}}{k_{1}+k_{2}}+\frac{k_{1}+k_{2}}{k_{2}}+\frac{k_{2}}{b}$

오른쪽의 합은 $\frac{b}{k_{2}}+\frac{k_{2}}{k_{1}+k_{2}}+\frac{k_{1}+k_{2}}{k_{1}}+\frac{k_{1}}{a}$

전체 합은 $\frac{a+k_{1}+k_{2}}{k_{1}}+\frac{b+k_{1}+k_{2}}{k_{2}}+\frac{k_{1}+k_{2}}{k_{1}+k_{2}}+\frac{k_{2}}{b}+\frac{k_{1}}{a}$

방금 구한 전체 합과 이전의 전체 합을 비교하면 3 차이가 나는 것을 확인할 수 있다. 새로 생긴 항은 자신의 왼쪽 항에 +1, 자기 자신에 의해 +1, 자신의 오른쪽 항에 +1을 함으로써 전체적으로 +3이 되었다는 사실을 알 수 있다.

이제 다 끝났다. 우리가 구하고자 하는 답을 $s_{n}$이라 하자.

$s_{n+1}=s_{n}+3\phi(n+1)/2$ ($n>=2$, $s_{1}=1$)

$\phi(n+1)$을 2로 나눈 이유는 기약 분수가 추가될 때 $1/2$의 양 쪽에 1개씩 추가되기 때문이다. 따라서 반만 더한다.

$$s_{n+1}=\frac{3}{2} \sum_{r=2}^{n+1} \phi(r) + 1$$

($1$은 $s_{1}$의 초기값이므로 더해준다.)

$s_{n+1}$을 2배하고 /2를 출력해줄 것이므로 실제 답은

$$2s_{n+1}=2+3 \sum_{r=2}^{n+1} \phi(r)$$

단, $n=1$일 때는 1을 출력하는 것은 예외 처리 하자.

 

여러 테케가 있으므로 전처리로 $\phi(r)$의 누적합을 미리 구해놓자. 코드는 아래에 있다.

 

코드 보기

#include<stdio.h>
typedef long long ll;
const ll SZ=10001;
ll phi[SZ];
ll f(ll n){
    ll s=1,i;
    for(i=2;i*i<=n;i+=2){
        if(n%i==0){
            n/=i;
            s*=i-1;
            while(n%i==0){
                s*=i;
                n/=i;
            }
        }
        if(i==2) i--;
    }
    if(n-1==0) return s;
    return s*(n-1);
}
int main(){
    ll i,T,n;
    for(i=2;i<SZ;i++){
        phi[i]=phi[i-1]+3*f(i);
    }
    scanf("%lld",&T);
    for(i=1;i<=T;i++){
        scanf("%lld %lld",&i,&n);
        if(n==1){
            printf("%lld 1\n",i);
            continue;
        }
        printf("%lld %lld/2\n",i,2+phi[n]);
    }
}