### Pandigital Fibonacci ends题号：104 难度： 25 中英对照

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.

### Code

import java.util.Arrays;

public final class p104 {

public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

public static String run() {
long f[]=new long;
long g[]=new long;
f=g=0;
f=g=1;
for(int i=2;i<1000000;i++){
f[i]=(f[i-1]+f[i-2])%1000000000;
if(g[i-1]*5<g[i-2])
g[i]=g[i-1]+g[i-2]/10;
else if(g[i-1]+g[i-2]>=1000000000000000000L)
g[i]=(g[i-1]+g[i-2])/10;
else
g[i]=g[i-1]+g[i-2];
String a=Long.toString(f[i]);
if(!check(a)) continue;
String b=Long.toString(g[i]).substring(0,9);
if(!check(b)) continue;
return Integer.toString(i);
}
return "NULL";
}
static private boolean check(String a){
if(a.length()!=9) return false;
boolean flag[]=new boolean;
for(int j=0;j<9;j++)flag[j]=false;
for(int j=0;j<9;j++)
if(a.charAt(j)=='0')
return false;
else if(flag[a.charAt(j)-'1'])
return false;
else
flag[a.charAt(j)-'1']=true;
return true;
}
}
329468
85ms