Farey Sequence(歐拉函數)
題意:給出式子F F中分子分母互質,且分子小於分母
例:
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}
求解 fn的元素個數、
分析:本題就是求解歐拉函數值的前n項和,直接求解歐拉函數值的方法不行,因為用此法就是O(n^2)復雜度,采用遞推式求解是O(nlogn)復雜度
代碼如下:
#include
#include