PE 104 Pandigital Fibonacci ends （數學fibonacci）

Pandigital Fibonacci ends

Problem 104

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−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 Fk 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;
}