HDU 4556 Stern-Brocot Tree
來源：程序員人生 發布時間：2016-09-25 09:01:19 閱讀次數：3062次
題目：點擊打開鏈接
Description
上圖是1棵Stern-Brocot樹，其生成規則以下：
從第1行到第n行，每行相鄰兩數a/b和c/d，產生中間數(a+c)/(b+d)，置于下1行中。將1行的分數（包括0/1,1/0），進行約分簡化，則每行（包括0/1,1/0,1/1），不會出現兩個相同的分數。若份子或分母大于n，則去掉該分數，將剩下的分數，從小到大排序，得到數列F。
現在請您編程計算第n行的數列F的個數。
Input
輸入包括多組測試用例，每組輸入數據是1個正整數n（n<=1000000）。
Output
對每組的測試數據n，請輸出第n行的數列F的個數。
這個題目就是想說明，SB樹和Farey序列的關系。
代碼就幾近不用再寫了，直接把我的博客略改便可。
代碼：
#include<iostream>
#include<stdio.h>
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
