題意：求SB樹第N層分母分子小于均等于N的數有多少？

?

搞清楚了SB Tree的性質，這道題就很容易了。因為SB Tree中的數均為最簡分數，所以篩一波歐拉函數即可。

#include<bits/stdc++.h> using namespace std; #define MAXN 1000000+10 int n,phi[MAXN],sum[MAXN]; void form(){phi[1]=1;for(int i=2;i<=1000000;i++)if(!phi[i])for(int j=i;j<=1000000;j+=i){if(!phi[j])phi[j]=j;phi[j]=phi[j]/i*(i-1);}for(int i=1;i<=1000000;i++)sum[i]=sum[i-1]+phi[i]; } int main(){form();while(~scanf("%d",&n))printf("%d\n",sum[n]*2+1);return 0; }

?

轉載于:https://www.cnblogs.com/NINGLONG/p/7698687.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。