首页 > 其他分享 >SP8547 题解

SP8547 题解

时间:2022-12-11 13:45:35浏览次数:53  
标签:数列 int 题解 long Fib SP8547

SP8547 题解

题意简述:给定 \(n\),找到能够使得辗转相除法执行 \(n\) 次的两个数,使得这两个数的和最小,输出这两个数。\(n\le10^{18}\)

分析:
对于这种题,一看就是猜结论的题,因为欧几里得算法最后的结束态即为:\((0,x)\),考虑倒推这个过程,在倒推过程中,由于欧几里得算法涉及取模,而我们所求为和最小,那么即我们仅仅让较大数不超过较小数的两倍即可,由此推理:

\[(0,x)->(1,x)->(x,x+1)->(x+1,2x+1)->(2x+1,3x+1)->(3x+1,5x+1)->…… \]

不妨设这个二元组为序列 \(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

相关文章

  • [NOIP2022] 喵了个喵 题解
    [NOIP2022]喵了个喵题解先考虑\(k=2n-2\),这个数字提示我们每个栈放两种颜色,剩下一个栈辅助操作。那么颜色被分为两类在栈底,可以通过操作2消去。在栈顶,可以通过操作1......
  • VUE3 API之reactive和ref常见问题解决
    reactive解构最深的一层,失去响应性问题<scriptsetuplang="ts">lettarget={a:{b:1}};lettarget1={c:1};constobj=reactive(target)constobj1=......
  • MySQL8.0登录提示caching_sha2_password问题解决方法
    背景用​​docker​​构建mysql容器后连接遇到以下问题问题Authenticationplugin'caching_sha2_password'cannotbeloaded:dlopen(/usr/local/mysql/lib/plugin/cachin......
  • 牛客题解——牛牛家的房子
    题目描述城市有n排n列的房子。牛牛在每个格点(x,y)[0≤x,y≤n]建了一所房子,冬天来了,(x,y)的室内温度为t[x*n+y]度。从(x1,y1)处的房子移动到(x2,y2)处的房子需要......
  • ABC281 DEF 简短题解
    G有时间想,但不太擅长这种图论计数,就摆了。Ex直接润。感觉这场打得很烂,全程梦游,吃了5发罚时,很棒。D-MaxMultiple给定\(n\)个数\(a_1\sima_n\),选出\(k\)个......
  • Atcoder-ABC281-DEF题解
    AtcoderBeginnerContest281D.MaxMultiple(DP)题意在长度为\(N\)的序列\(A\)中,找到\(K\)个元素其和为\(D\)的倍数,找出满足要求最大的和,没有则返回-1。数......
  • 常见问题解决 --- IDEA报错 org.apache.jasper.servlet.TldScanner.scanJars 至少有一
    问题描述 问题原因tomcat版本太高,代码使用的是低版本 解决办法降低tomcat版本。或者修改代码到高版本。  ......
  • [POJ1734]Sightseeing 观光之旅 题解
    无向图的最小环问题,前置芝士:\(\text{Floyd}\)传送门题目描述给定一张无向图,求图中一个至少包含\(3\)个点的环,环上的节点不重复,并且环上的边的长度之和最小。你需要......
  • 问题解决系列:io.lettuce.core.RedisCommandExecutionException_ CLUSTERDOWN
    问题场景程序调用​​redis​​集群,总是间歇性地提示报错,报错提示如下:org.springframework.data.redis.RedisSystemException:Errorinexecution;nestedexceptionisio......
  • P2018:消息传递题解——二次扫描与换根
    消息传递题面题目描述巴蜀国的社会等级森严,除了国王之外,每个人均有且只有一个直接上级,当然国王没有上级。如果A是B的上级,B是C的上级,那么A就是C的上级。绝对不会出现这样......