首页 > 代码库 > hdu 3054 Fibonacci 找循环节的公式题
hdu 3054 Fibonacci 找循环节的公式题
Fibonacci
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Problem Description
We know the Fibonacci Sequence
F1=1,F2=1,F3=2,F4=3,F5=5,
...
Fx = Fx-1+Fx-2
We want to know the Mth number which has K consecutive "0" at the end of Fx.
For example,
F15=610
It is the first number which has only one "0" at the end.
F300=222232244629420445529739893461909967206666939096499764990979600.
It is the second number which has two "0" at the end.
Of course, the Fx may be very large if M and K are big. So we only want to know the subscript of Fx (it means the "x" For a given M and K)
F1=1,F2=1,F3=2,F4=3,F5=5,
...
Fx = Fx-1+Fx-2
We want to know the Mth number which has K consecutive "0" at the end of Fx.
For example,
F15=610
It is the first number which has only one "0" at the end.
F300=222232244629420445529739893461909967206666939096499764990979600.
It is the second number which has two "0" at the end.
Of course, the Fx may be very large if M and K are big. So we only want to know the subscript of Fx (it means the "x" For a given M and K)
Input
Input includes multiple cases.
First line is the number of case x
The next x lines: Each line contains two integer number, K and M, divided by a space.
First line is the number of case x
The next x lines: Each line contains two integer number, K and M, divided by a space.
Output
For each case:
Print a integer number in a line, is the Mth number which has K consecutive 0s at the end of Fx. (You can believe the answer is smaller than 2^31);
Print a integer number in a line, is the Mth number which has K consecutive 0s at the end of Fx. (You can believe the answer is smaller than 2^31);
Sample Input
31 12 22 5
Sample Output
15300900
Source
2009 Multi-University Training Contest 15 - Host by BUAA
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=4e6+10,inf=1e9+10,MOD=1000;const ll INF=1e18+10;int a[100]={1,15,150,750,7500,75000,750000,7500000,75000000,750000000};int main(){ int T; scanf("%d",&T); while(T--) { int k,m; scanf("%d%d",&k,&m); if(k==2) printf("%d\n",((m-1)/4*5+1)*a[k]+((m-1)%4)*a[k]); else printf("%d\n",((m-1)/9*10+1)*a[k]+((m-1)%9)*a[k]); } return 0;}
hdu 3054 Fibonacci 找循环节的公式题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。