洛谷 P1306 斐波那契公约数 题解
2024-08-31 11:12:53
结论:gcd(F[n],F[m])=F[gcd(n,m)];
F[n]=a和F[n+1]=b
F[n+2]=a+b,F[n+3]=a+2b,…F[m]=F[m?n?1]a+F[m?n]b
F[n]=a,F[n+1]=b,F[m]=F[m?n?1]a+F[m?n]
F[m]=F[m?n?1]?F[n]+F[m?n]?F[n+1]
gcd(F[n],F[m])=gcd(F[n],F[m?n?1]?F[n]+F[m?n]?F[n+1])
gcd(F[n],F[m])=gcd(F[n],F[m?n]?F[n+1])
引理:gcd(F[n],F[n+1])=1
证明:gcd(F[n],F[n+1])=gcd(F[n],F[n+1]?F[n])=gcd(F[n],F[n?1])=......=gcd(f[1],f[2]);
gcd(F[n],F[n+1])=1;
gcd(F[n],F[m])=gcd(F[n],F[m?n]?F[n+1]);
gcd(F[n],F[m])=gcd(F[n],F[m?n]);
即gcd(F[n],F[m])=gcd(F[n],F[mmodn]);
则gcd(F[n],F[m])=gcd(F[nmodm1],F[m1]);
不难发现,整个递归过程其实就是在求解gcd(n,m)
最后递归到出现F[0],那么此时的f[n]就是答案;
gcd(F[n],F[m])=F[gcd(n,m)];
最新文章
- android mk odex问题 push apk 不生效
- 安装和使用Linux花生壳(公网版)
- Linux vmstat字段解析
- [Effective JavaScript 笔记]第67条:绝不要同步地调用异步的回调函数
- 2016.6.23 PHP实现新闻发布系统主体部分
- Weak Pair---hud5877大连网选(线段树优化+dfs)
- python tools: iPython Notebook
- TMS320C54x系列DSP的CPU与外设——第5章 数据寻址
- JAVA:二进制(原码 反码 补码),位运算,移位运算,约瑟夫问题(5)
- iOS 非ARC基本内存管理系列 3-循环retain和@class
- 引用的时候js不能使用虚拟路劲,调试时用排除法测试
- web.xml 配置的详解
- Fatal error: Call to undefined function mysql_connect()
- (知识点)JavaScript原型和原型链
- 201521123003《Java程序设计》第6周学习总结
- InnoDB 存储引擎的特点及优化方法
- BP算法的矩阵推导
- WPFのDecorator 、Adorner和AdornerDecorator
- c数组
- ibatis中的安全问题