プロジェクトオイラー
http://projecteuler.net/index.php
Q104.
フィボナッチ数で、頭の9桁とお尻の9桁がともに1〜9を全て使っている最初の数の項番号
特に工夫する余地もないし、素直にPythonで組んでみたが、なかなか返ってこない。仕方がないので、はじめてC++で組んでみた。多倍長整数をvector
これでも遅ければ、色々工夫しようと思っていたが、20秒くらいで返ってきたのでやめた。
#include
#includeusing namespace std;
typedef vector
LONG;
const int N = 1000000000;// a>=bでなければならない
LONG add(const LONG& a, const LONG& b) {
LONG c = a;
const int n = (int)b.size();
const int m = (int)c.size();
for(int i = 0; i < n; i++) {
c[i] += b[i];
if(c[i] > N) {
c[i] -= N;
if(i == m - 1)
c.push_back(1);
else
c[i+1] += 1;
}
}
return c;
}int getLast(const LONG& a) {
return a.front();
}int getFirst(const LONG& a) {
int s = (int)a.size();
int n = a.back();
if(s == 1) {
return n;
}
else {
if(n >= N) {
return n;
}
else {
int m = 10;
while(n >= m)
m *= 10;
return n * (N / m) + (a[(int)a.size()-2] / m);
}
}
}void print(const LONG& a) {
printf("%d", a.back());
for(int i = 0; i < (int)a.size() - 1; i++)
printf("%09d", a[i]);
printf("\n");
}class gen_Fibonacci {
LONG a, b;
int k;
public:
gen_Fibonacci() {
a = LONG(1, 1);
b = LONG(1, 1);
k = 0;
}
LONG operator()() {
k++;
if(k == 1)
return a;
else if(k == 2)
return b;
else if(k & 1) {
LONG c = add(a, b);
b = c;
return c;
}
else {
LONG c = add(b, a);
a = c;
return c;
}
}
int nth() const {
return k;
}
};bool is_pandigital(int n) {
int a[10];
for(int i = 0; i < 10; i++)
a[i] = 0;
for(int i = 0; i < 9; i++) {
int d = n % 10;
if(d == 0)
return false;
else if(a[d] == 1)
return false;
else
a[d] = 1;
n /= 10;
}
return true;
}int main() {
gen_Fibonacci g;
for(int i = 0; ; i++) {
LONG a = g();
if(is_pandigital(getLast(a))) {
if(is_pandigital(getFirst(a))) {
cout << g.nth() << endl;
break;
}
}
}
}
