PE 104 Pandigital Fibonacci ends （数学fibonacci）

╰+攻爆jí腚メ 2022-07-13 01:17 72阅读 0赞

## Pandigital Fibonacci ends ##

### Problem 104 ###

The Fibonacci sequence is defined by the recurrence relation:

> F*n* = F*n*−1 \+ F*n*−2, where F1 = 1 and F2 = 1.

It turns out that F541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that F*k* is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find *k*.

题解：让你求出第几个fibonacci的前9位数和后九位数都是1-9的排列。

求后9位就mod 1000000000。

然后前九位就从前18位中取9位就行了。

取前18位：

if(a * 5 < b){
    		return a + b/10;
    	}
    	if(a + b >= 10000000000000000) return (a + b) /10;
    	return a+b;

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll f[1000000];
    ll g[1000000];
    ll sum(ll a,ll b) 
    {
    	if(a * 5 < b){
    		return a + b/10;
    	}
    	if(a + b >= 10000000000000000) return (a + b) /10;
    	return a+b;
    }
    string tostring(ll a)
    {
    	string s;
    	while(a)
    	{
    		s += (a % 10+'0');
    		a/=10;
    	}
    	reverse(s.begin(),s.end());
    	return s;
    }
    int main()
    {
    	f[0]=0;
    	g[0]=0;
    	f[1]=1;
    	g[1]=1;
    	for(int i=2;i<1000000;i++)
    	{
    		f[i]=(f[i-1]+f[i-2])%1000000000;
    		g[i]=sum(g[i-1],g[i-2]);
    		string s=tostring(f[i]);
    		string t=tostring(g[i]).substr(0,9);
    		sort(s.begin(),s.end());
    		sort(t.begin(),t.end());
    		if(s==t)
    		{
    			if(t=="123456789")
    			{
    				cout<<"第 "<<i<<" 个fibonacci:";
    				cout<<g[i]<<" + "<<f[i]<<endl; 
    			}
    		}
    	}
    	return 0;
    }