Stern-Brocot Tree

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)

Problem Description
　　
　　上圖是一棵Stern-Brocot樹，其生成規(guī)則如下：
　　從第1行到第n行，每行相鄰兩數(shù)a/b和c/d，產(chǎn)生中間數(shù)(a+c)/(b+d)，置于下一行中。將一行的分?jǐn)?shù)（包括0/1,1/0），進(jìn)行約分簡化，則每一行（包括0/1,1/0,1/1），不會出現(xiàn)兩個(gè)相同的分?jǐn)?shù)。若分子或者分母大于n，則去掉該分?jǐn)?shù)，將剩下的分?jǐn)?shù)，從小到大排序，得到數(shù)列F。
　　現(xiàn)在請您編程計(jì)算第n行的數(shù)列F的個(gè)數(shù)。

Input 輸入包含多組測試用例，每組輸入數(shù)據(jù)是一個(gè)正整數(shù)n（n<=1000000）。
Output 對于每組的測試數(shù)據(jù)n，請輸出第n行的數(shù)列F的個(gè)數(shù)。
Sample Input 1 2 4 6
Sample Output 3 5 13 25 仔細(xì)看圖可以發(fā)現(xiàn)：對于每一行都可以看成是關(guān)于1/1對稱的兩部分，所以只需求出1/1左邊的個(gè)數(shù)就可求出這一行的個(gè)數(shù)。而左邊全部都是真分?jǐn)?shù)，分母為x的真分?jǐn)?shù)的個(gè)數(shù)就是x的歐拉函數(shù)值。n最大為1000000，所以可以遞推打表。 #include<cstdio> const int N = 1000001; int e[N]; __int64 a[N], res = 0; void euler() {for(int i = 2; i < N; i++)e[i] = 0;e[1] = 1;for(int i = 2; i < N; i++)if(!e[i]){for(int j = i; j < N; j += i){if(!e[j])e[j] = j;e[j] = e[j] / i * (i-1);}} } int main() {int i, n;euler();for(i = 1; i < N; i++){res += e[i];a[i] = res * 2 + 1;}while(~scanf("%d", &n))printf("%I64d\n", a[n]);return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的hdu 4556 Stern-Brocot Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。