SP8547 题解
题意简述:给定 \(n\),找到能够使得辗转相除法执行 \(n\) 次的两个数,使得这两个数的和最小,输出这两个数。\(n\le10^{18}\)
分析:
对于这种题,一看就是猜结论的题,因为欧几里得算法最后的结束态即为:\((0,x)\),考虑倒推这个过程,在倒推过程中,由于欧几里得算法涉及取模,而我们所求为和最小,那么即我们仅仅让较大数不超过较小数的两倍即可,由此推理:
不妨设这个二元组为序列 \(f\),\(f(0)\) 表示 \((0,x)\),以此类推。记 \(f(n)_0,f(n)_1\) 分别表示二元组 \(f(n)\) 的较小值与较大值。
容易发现:\(f(n+1)_0=f(n)_1,f(n+1)_1=f(n)_0+f(n)_1\),这很像斐波那契数列。再来,要使 \(f(n)_0+f(n)_1\) 最小,就要使最初的 \(x\) 最小,显然在合法的情况下,\(x=1\)。(\(x=0\) 时,式子并不成立。此时再看,这个数列变成了:\((0,1),(1,1),(1,2),(2,3)…\),不难看出,\(f(n)=(Fib_n,Fib_{n+1})\)。这里的 \(Fib\) 表示斐波那契数列,规定第零项为 \(0\)。
问题变成了快速求解斐波那契数列,矩阵快速幂即可。
这里注意特判:也即当 \(n=0\) 的时候,\((0,0)\) 才是最优决策,再特判 \(n=1\),因为 \(f(1),f(2)\) 实质上都只需要一次,而 \(f(n)(n>1)\) 需要 \(n-1\) 次。在实际操作的时候,将答案变为:\(A^n\times[1,1]\) 即可,\(A\) 为辅助矩阵。
#define int long long
const long long p=1000000007;
int f[2],a[2][2],ans[2][2],lst[2];
void mul(int a[2][2],int b[2][2]){
int c[2][2];
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
c[i][j]=0;
for(int k=0;k<2;k++){
c[i][j]+=a[i][k]*b[k][j];
if(c[i][j]>p)c[i][j]%=p;
}
}
}
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
a[i][j]=c[i][j];
}
void power(int a[2][2],int b){
ans[0][0]=ans[1][1]=1;
while(b){
if(b&1)mul(ans,a);
b>>=1;
mul(a,a);
}
}
signed main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
if(n==1){
cout<<"2"<<endl;
continue;
}
if(n==0){
cout<<"0"<<endl;
continue;
}
memset(a,0,sizeof a);
memset(f,0,sizeof f);
memset(ans,0,sizeof ans);
memset(lst,0,sizeof lst);
a[0][1]=1;
a[1][1]=a[1][0]=1;
power(a,n);
f[0]=f[1]=1;
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
lst[j]+=f[k]*ans[k][j];
if(lst[j]>p)lst[j]%=p;
}
}
cout<<(lst[0]+lst[1])%p<<endl;
}
}
标签:数列,int,题解,long,Fib,SP8547
From: https://www.cnblogs.com/oierpyt/p/16973597.html