这题目有点恶心,推出来公式:
s = t ∗ ( s q r t ( 3 ∗ ( t − 2 ) ∗ ( t + 2 ) ) / 4 s=t*(sqrt(3*(t-2)*(t+2))/4s=t∗(sqrt(3∗(t−2)∗(t+2))/4
通过 打表知道规律:
ans[i]=4*ans[i-1]-ans[i-2];
因为数据4–10^30 3030
所以用高精度或者int128;
高精度代码:
#include<bits/stdc++.h> using namespace std; const int N=1100; vector<int>ans[N]; string n; int T; vector<int> sub(vector<int>a,vector<int>b) { int t=0; vector<int>res; for(int i=0;i<a.size();i++) { t=a[i]-t; if(i<b.size()) t-=b[i]; res.push_back((t+10)%10); if(t<0) t=1; else t=0; } while(res.size()>1&&res.back()==0) res.pop_back(); return res; } vector<int>mul(vector<int>&a,int b) { int t=0; vector<int>res; for(int i=0;i<a.size()||t;i++) { if(i<a.size()) t+=a[i]*b; res.push_back(t%10); t/=10; } while(res.size()>1&&res.back()==0) res.pop_back(); return res; } bool compare(vector<int>&a,vector<int>&now) { if(a.size()!=now.size()) return a.size()<now.size(); for(int i=a.size()-1;i>=0;i--) { if(a[i]<now[i]) return 1; else if(a[i]>now[i]) return 0; } return 0; } int main() { cin>>T; ans[1].push_back(4); ans[2].push_back(4); ans[2].push_back(1); for(int i=3;i<=105;i++) { ans[i]=sub(mul(ans[i-1],4),ans[i-2]); } while(T--) { cin>>n; vector<int>now; for(int i=n.size()-1;i>=0;i--) now.push_back(n[i]-'0'); int i=1; while(compare(ans[i],now)) { i++; } for(int j=ans[i].size()-1;j>=0;j--) { cout<<ans[i][j]; } cout<<endl; } return 0; }
__int128版本:
#include<bits/stdc++.h> using namespace std; const int N=1100; __int128 f[N],n; int T; __int128 read() { __int128 x = 0, f = 1; char ch = getchar(); while (!isdigit(ch) && ch != '-')ch = getchar(); if (ch == '-')f = -1; while (isdigit(ch))x = x * 10 + ch - '0', ch = getchar(); return f * x; } inline void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0'); } int main() { cin>>T; f[1]=4; f[2]=14; for(int i=3;i<=105;i++) { f[i]=4*f[i-1]-f[i-2]; } while(T--) { n=read(); int i=1; while(f[i]<n) i++; print(f[i]); cout<<"\n"; } return 0; }