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]$

$\sum_{i=1}^nf_{n/i}=\sum_{i=1}^ni=n*(n+1)/2$

$f_n=n*(n+1)/2-\sum_{i=2}^nf_{n/i}$

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;
}