题目链接

Farey Sequence

题目描述

The Farey Sequence Fn for any integer $n$ with $n \ge 2$ is the set of irreducible rational numbers $a/b$ with $0 < a < b \le n$and $gcd$($a,b$)$ = 1$ arranged in increasing order. The first few are
$F_2 = {1/2}$
$F_3 = {1/3, 1/2, 2/3}$
$F_4 = {1/4, 1/3, 1/2, 2/3, 3/4}$
$F_5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}$

You task is to calculate the number of terms in the Farey sequence Fn.

输入格式

There are several test cases. Each test case has only one line, which contains a positive integer $n$ ($2 \ge n \ge 10^6$). There are no blank lines between cases. A line with a single $0$ terminates the input.

输出格式

For each test case, you should output one line, which contains $N$($n$) ---- the number of terms in the Farey sequence $F_n$.

样例输入

2
3
4
5
0

样例输出

1
3
5
9

题解

$F_n=\sum_{i=1}^n\sum_{j=i+1}^n[gcd(i,j)==1]$
我们假设$f_n$为$n$以内$gcd$为$1$的对数,视($i,j$)和($j,i$)相同,包括($1,1$)。
那么$n$以内$gcd$为$2$的对数为$f_{n/2}$
以此类推,$n$以内$gcd$为$i$的对数为$f_{n/i}$
那么我们可以得到如下等式:
$\sum_{i=1}^nf_{n/i}=\sum_{i=1}^ni=n*(n+1)/2$
因为$f_n$中($i,j$)和($j,i$)不重复计算,所以上述等式成立。
我们再把等式左边的$f_n$提出来,
$f_n=n*(n+1)/2-\sum_{i=2}^nf_{n/i}$
那么我们就得到了$f_n$的递推式,我们考虑到$f_n=F_n+1$,因为题目中要求不包含($1,1$)
所以我们可以用递推式求$f_n$,因为$n \le 10^6$,所以我们记忆化一下就可以过了。
ps:据说也可以用欧拉函数前缀和做,这里就不多讲了QWQ。

#include<cstdio>
using namespace std;
int n;
long long f[1000009];
long long fd(long long x){
    if(f[x]!=0) return f[x];
    f[x]=x*(x+1)/2;
    for(long long i=2;i<=x;i++){
        f[x]-=((x/(x/i))-i+1)*fd(x/i);//因为一段区域内x/i相等,fd(x/i)相等,所以可以优化一下
        i=x/(x/i);
    }
    return f[x];
}
int main(){
    f[1]=1;
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        printf("%lld\n",fd(n)-1);
    }
    return 0;
}