Farey Sequence
题意翻译
## 题目描述
对于一个大于 $1$ 的整数 $n$ ,定义Farey序列 $F_n$ 为一个分数集合 $\{{a/b},0<a<b\leq n$ 且 $\gcd(a,b)=1\}$
例如,前几项为
$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\}$
每次给定 $n$ ,求 $F_n$ 中分数的个数
## 输入输出格式
### 输入格式:
每行一个数 $n$ ,以 $0$ 作为输入结尾。行数最多 $20000$ 。
### 输出格式:
每行一个数,为 $F_n$ 中分数的个数。
感谢@flashess 提供的翻译
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=862&page=show_problem&problem=4878
[PDF](https://uva.onlinejudge.org/external/129/p12995.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12995/01cce3f4be45bc505a588c99b148e4e463572237.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12995/a24a6fdbcf9578f9b19da4c7d4ce0cc32f25aa47.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12995/acd32b4a981e98545dcbbee0d0f297cd94de8869.png)
输入输出样例
输入样例 #1
1
4
0
输出样例 #1
0
5