Description
Input
输入包含多组测试用例,每组输入数据是一个正整数n(n<=1000000)。Output
对于每组的测试数据n,请输出第n行的数列F的个数。Sample Input
1 2 4 6
Sample Output
3 5 13 25
这个题目就是想说明,SB树和Farey序列的关系。
代码:
#include#include using namespace std; long long phi[1000001]; void get_phi() { for (int i = 1; i <= 1000000; i++)phi[i] = i; for (int i = 2; i <= 1000000; i++) { if (phi[i] == i)for (int j = i; j <= 1000000; j += i)phi[j] = phi[j] / i*(i - 1); phi[i] += phi[i - 1]; } } int main() { get_phi(); int n; while (scanf("%d",&n)!=-1)printf("%llu\n", phi[n]*2+ 1); return 0; }