思路

小老弟树产生的分数都是互质的，由于题目规定第n行产生的分子分母不超过n,而且经过简单推导可以猜测第n代可以表示出分子分母不超过n的所有互质对，那么我们就可以用欧拉函数来做。直接规定第n代产生的数就是欧拉函数的n行前缀和。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=1e6+7;
const int mod=1e9+7;

int pri[N],is_pri[N],phi[N],sum[N],cnt=0;
void init(){
	is_pri[1]=1;phi[1]=sum[1]=1;
	for(int i=2;i<N;i++){
		if(!is_pri[i]) pri[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&pri[j]*i<N;j++){
			is_pri[i*pri[j]]=1;
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}else phi[i*pri[j]]=phi[i]*(pri[j]-1); 
		}
	}
	for(int i=2;i<N;i++) sum[i]=sum[i-1]+phi[i];
}

int t,n,res;
signed main(){
	init();
	cin>>t;
	while(t--){
		cin>>n;
		cout<<sum[n]+1<<"\n";
 	}
	return 0;
}