首页 > 代码库 > 数论 ： 高精度 --- UVa 10183 : How Many Fibs ?
数论 ： 高精度 --- UVa 10183 : How Many Fibs ?
How many Fibs?
Description
Recall the definition of the Fibonacci numbers:
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].
f1 := 1n-1
f2 := 2
fn := f
+ fn-2
(n>=3)
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].
Input
The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a=b=0. Otherwise, a<=b<=10100. The numbers a and b are given with no superfluous leading zeros.
Output
For each test case output on a single line the number of Fibonacci numbers fi with a<=fi<=b.
Sample Input
10 1001234567890 98765432100 0
Sample Output
54
Mean:
给定两个整数a和b，统计区间[a,b]内有多少个斐波那契数。
analyse:
T由于这题输入的范围达到了10^100，必须要用高精度来做。
我们先把10^100以内的斐波那契数全部求出来，然后输入的sta,en后进行位置查找，最后把sta、en的位置相见就的答案。
Time complexity：O(n)
Source code：
/* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---‘\____ .‘ \\| |// `. / \\||| : |||// / _||||| -:- |||||- | | \\\ - /// | | | \_| ‘‘\---/‘‘ | | \ .-\__ `-` ___/-. / ___`. .‘ /--.--\ `. . __ ."" ‘< `.___\_<|>_/___.‘ >‘"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / /======`-.____`-.___\_____/___.-`____.-‘====== `=---=‘^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^............................................. 佛祖镇楼 BUG辟易 佛曰: 写字楼里写字间，写字间里程序员； 程序人员写程序，又拿程序换酒钱。 酒醒只在网上坐，酒醉还来网下眠； 酒醉酒醒日复日，网上网下年复年。 但愿老死电脑间，不愿鞠躬老板前； 奔驰宝马贵者趣，公交自行程序员。 别人笑我忒疯癫，我笑自己命太贱； 不见满街漂亮妹，哪个归得程序员？ *///Memory Time// 1347K 0MS// by : Snarl_jsb#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define MAX 1100#define LL long longusing namespace std;vector<string> fibs;string fibs_add(string f1,string f2){ string buff; int carry=0,len1=f1.length(),len2=f2.length(); for(int i=0;i<len1;i++) { carry=(f1[i]-‘0‘)+(f2[i]-‘0‘)+carry; char c=carry%10+‘0‘; carry/=10; buff.push_back(c); } for(int i=len1;i<len2;i++) { carry=(f2[i]-‘0‘)+carry; char c=carry%10+‘0‘; carry/=10; buff.push_back(c); } if(carry) buff.push_back(‘1‘); return buff;}void fill_fibs(){ string f1,f2; f1.push_back(‘1‘); f2.push_back(‘1‘); fibs.push_back(f1); fibs.push_back(f2); while(f2.length()<105) { string tmp=fibs_add(f1,f2); f1=f2; f2=tmp; fibs.push_back(f2); } fibs[0]="0"; int Size=fibs.size(); for(int i=0;i<Size;i++) reverse(fibs[i].begin(),fibs[i].end());}int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout);// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout); fill_fibs(); string sta,en; while(cin>>sta>>en,sta[0]-‘0‘||en[0]-‘0‘) { int i=1,ans=0; while(1) { if(fibs[i].length()>sta.length()) break; else if(fibs[i].length()==sta.length()&&fibs[i]>=sta) break; i++; } while(1) { if(fibs[i]==en) {ans++;break;} if(fibs[i].length() > en.length()) break; else if(fibs[i].length() == en.length() && fibs[i]>en) break; i++; ans++; } cout<<ans<<endl; } return 0;}
数论 ： 高精度 --- UVa 10183 : How Many Fibs ?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。