连分数渐近分数的实现与大数处理 问题描述在计算连分数的渐近分数时递推公式如下pkak⋅pk−1pk−2,qkak⋅qk−1qk−2p_k a_k \cdot p_{k-1} p_{k-2}, \quad q_k a_k \cdot q_{k-1} q_{k-2}pk​ak​⋅pk−1​pk−2​,qk​ak​⋅qk−1​qk−2​初始条件为$ p_{-1} 1, p_0 a_0 $- $ q_{-1} 0, q_0 1 $当 $ n \leq 100 $ 时分子和分母的值可能达到 $ 10^{500} $远远超出long long的范围因此必须使用大数运算。 大数设计为了处理非常大的整数我们采用以下策略压 9 位将数字按每 9 位一组存储基为 $ 10^9 $。vectorint存储低位在前便于操作。支持两种基本运算大数 × 小整数利用long long处理进位时间复杂度 $ O(L) $。大数 大数逐位相加并处理进位时间复杂度 $ O(L) $。⚙️ 算法复杂度- 总位数为 $ O(n) $。每次递推为 $ O(L) $总复杂度为 $ O(n^2) $。- 对于 $ n100 $完全可以在合理时间内完成。—### 示例代码C-#includecstdio-#includevector-usingnamespacestd;-constintA[]{3,7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,6,1,1,1,5,1,82,1,159,1,2,1,3,1,1,1,2,1,1,1,1,2,1,1,1,3,1,1,1,1,1,2,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};-structB{-vectorintd;-B(intx0){-while(x){-d.push_back(x%1000000000);-x/1000000000;-}-if(d.empty())d.push_back(0);-}-Boperator*(intx)const{-B r;-r.d.clear();-longlongc0;-for(inti0;i(int)d.size()||c;i){-if(i(int)d.size())c(longlong)d[i]*x;-r.d.push_back(c%1000000000);-c/1000000000;-}-returnr;-}-Boperator(constBo)const{-B r;-r.d.clear();-intc0;-intnmax(d.size(),o.d.size());-for(inti0;in||c;i){-intsc;-if(i(int)d.size())sd[i];-if(i(int)o.d.size())so.d[i];-r.d.push_back(s%1000000000);-cs/1000000000;-}-returnr;-}-voidprint(){-printf(%d,d.back());-for(inti(int)d.size()-2;i0;i--){-printf(%09d,d[i]);-}-}-};-intmain(){-intn;-scanf(%d,n);-Bp0(A[0]),p1(1),q0(1),q1(0);-for(intk1;kn;k){-B tpp0*A[k]p1;-B tqq0*A[k]q1;-p1p0;-p0tp;-q1q0;-q0tq;-}-p0.print();-putchar(/);-q0.print();-puts();-}-