传送门
a - farey sequence
time limit:1000ms memory limit:65536kb 64bit io format:%i64d
& %i64u
submit status
description
the farey sequence fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. the first few are
f2 = {1/2}
f3 = {1/3, 1/2, 2/3}
f4 = {1/4, 1/3, 1/2, 2/3, 3/4}
f5 = {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.
input
there are several test cases. each test case has only one line, which contains a positive integer n (2 <= n <= 10 6). there are no blank lines between cases. a line with a single 0 terminates the input.
output
for each test case, you should output one line, which contains n(n) ---- the number of terms in the farey sequence fn.
sample input
sample output
题目大意：
就是求一个f(n)的中元素的个数。
解题思路：
首先我们分析一下题目，我们一看就是关于欧拉函数的题，就是求<=b中与b互素的个数，但是我们别忘记还得加上phi(<n)的值，所以这个问题就是求欧拉函数的和的问题，然后我们如果用正常的做法也就是暴力做的话 会超时的（我试过了/笑cry），所以我们要找到更快速的方法
——筛法，其实这个筛法就是跟素数筛差不多的，也算是又学了一个知识点
code：