UVa 10236 The Fibonacci Primes：斐波那契素数

UVa 10236 The Fibonacci Primes：斐波那契素数2014-07-28 synapse7

10236 - The Fibonacci Primes

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1177

注意此题的描述和维基百科上Fibonacci Prime的描述不同。

上面加着重符的文字说明：可以用类似素数筛的方式筛出Fibonacci Prime。

但是，定理“若b|a，则fb|fa”并不能推出“若p是质数，则fp是Fibonacci Prime”。

要证明这一点，我们可以证明“若fb|fa，则b|a”（详见《具体数学》P247及《Proofs that Really Count: The Art of Combinatorial Proof》P12）

完整代码：

/*0.022s*/#include<cstdio>const int maxn = 249450;int fp[22001];bool vis[maxn];int main（）{long long a = 0, b = 1, tmp, i, j;int n, cp;for （cp = 1, i = 2; cp < 22001; ++i）{tmp = a + b, a = b, b = tmp;if （b >= 1e18） b /= 10, a /= 10;if （！vis[i]）{tmp = b;while （tmp >= 1e9） tmp /= 10;fp[cp++] = tmp;for （j = i * i; j < maxn; j += i） vis[j] = true;}}//printf（"%lld
",i）;fp[1] = 2, fp[2] = 3;while （~scanf（"%d", &n））printf（"%d
", fp[n]）;return 0;}