算法至美

用户名：uq_54514514336

访问量：7775

签　名：

等　　级
排　　名	1356
经　　验	2954
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1235-输出前k大的数-题解（各语言代码）
浏览：543

数列有序-题解（Python代码）
浏览：177

[编程入门]水仙花数判断-题解（各语言代码）
浏览：84

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

信息学奥赛一本通T1642-Fibonacci 第 n 项-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-05-25 20:25:14 浏览：220　|　评论：0　

原题链接：信息学奥赛一本通T1642-Fibonacci 第 n 项

计算斐波那契数列的方法有很多
这里仅介绍一种高效的算法
根据斐波那契数列定义：
$$Fib(n)=Fib(n-1)+Fib(n-2)$$
易得：
$$\begin{cases}Fib(2n+1)=4Fib(n)^2-Fib(n-1)^2+2(-1)^n\\\Fib(2n)=3Fib(n)^2-2Fib(n-1)^2+2(-1)^n\\\Fib(2n-1)=Fib(n)^2+Fib(n-1)^2\end{cases}$$
求Fib(n)时，根据n的奇偶带入式子，迭代求解
时间复杂度O(log n)，空间复杂度O(1)
**C++**
```cpp
#include<bitset>
#include<iostream>
using namespace std;
int main(){
	struct T{long long x,y,z;T(long long x,long long y,long long z):x(x),y(y),z(z){}}t(0,1,2);
	long long n,m,i;
	cin>>n>>m;
	i=__lg(n);
	bitset<64>s(n);
	do{
		t.x*=t.x;
		t.y*=t.y;
		t=s.test(i)?T(((t.x<<2)-t.y+t.z)%m,((t.x-t.y<<1)+t.x+t.z)%m,-2):T(((t.x-t.y<<1)+t.x+t.z)%m,(t.x+t.y)%m,2);
	}while(i--);
	cout<<(t.x<0?m+t.x:t.x);
}
```
**java**
```java
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int n = in.nextInt(), m = in.nextInt();
		in.close();
		System.out.print(Math.floorMod(Integer.toBinaryString(n).chars().mapToObj(i->i!='0').reduce(new long[]{0,1,2},(a,b)->{
			final long x = a[0] * a[0], y = a[1] * a[1], z = a[2];
			return b ? new long[] {((x<<2)-y+z) % m, ((x-y<<1)+x+z) % m, -2} : new long[] {((x-y<<1)+x+z) % m, (x+y) % m, 2};
		}, (a, b) -> null)[0], m));
	}
}
```
**python**
```python
from functools import reduce
print((lambda n,m:reduce(lambda a,b:(lambda x,y,z:(lambda p,q:(((p<<2)-q+z)%m,((p-q<<1)+p+z)%m,-2) if b!='0' else (((p-q<<1)+p+z)%m,(p+q)%m,2))(x*x,y*y))(*a),bin(n)[2:],(0,1,2)))(*map(int,input().split()))[0])
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

信息学奥赛一本通T1642-Fibonacci 第 n 项-题解（各语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

【计算两点间的距离】（C语言代码）

C语言训练-数字母（C语言代码）

打印十字图（C语言代码）

数组与指针的问题

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （Java代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

信息学奥赛一本通T1642-Fibonacci 第 n 项-题解（各语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

【计算两点间的距离】 （C语言代码）

C语言训练-数字母 （C语言代码）

打印十字图 （C语言代码）

数组与指针的问题

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

【计算两点间的距离】（C语言代码）

C语言训练-数字母（C语言代码）

打印十字图（C语言代码）