BZOJ5104: Fib数列

### Description
Fib数列为1,1,2,3,5,8...
求在Mod10^9+9的意义下，数字N在Fib数列中出现在哪个位置
无解输出-1
### Input
一行，一个数字N，N < = 10^9+9

### Output
如题

### Sample Input
3
### Sample Output
4

$10^9+9$明示$5$有二次剩余。

考虑$Fib$的通项公式:
$$f_n=\frac{1}{\sqrt 5}\left (\left (\frac{1+\sqrt 5}{2}\right)^n-\left (\frac{1-\sqrt 5}{2}\right)^n\right )$$

我们设$t = \left (\frac{1+\sqrt 5}{2}\right)^n$
那么：
$$\sqrt 5 f_n=t^n-(-1)^n\left(\frac{1}{t}\right)^n$$

分奇偶性讨论，然后用求根公式解出$x=t^n$。
现在我们只要找到最小的指定奇偶性的$n$使得$x=t^n$就好了。
一种方法是用$BSGS$分奇偶性记录两个$map$，根据需要的奇偶性分别查询。
还有一种方法比较具有推广性，设$BSGS$得到的最小解为$b$，考虑$t^n=x(mod\ p)$的所有解$n$一定可以表示成为$n=b(mod\ c)$

这个比较显然，因为只要存在$t^c=1(mod\ p)$就可以让解循环。
根据费马小定理，可以知道一定有$c|p-1$。
这样我们直接枚举$p-1$的约数$log n$判断即可求出$c$。

然而我两个方法都没有用
偷了个懒，$BSGS$出最小的解判奇偶，居然就过了= =。

```
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<map>
#include<cmath>
#define LL long long
using namespace std;
 
namespace NT {
    const int mod = 1e9 + 9;
    const int inf = 0x3f3f3f3f;
    int w2, G;
    int Rand() {return rand();}
    void init() {srand(20020327);}
    inline int Plus(const int &a, const int &b) {
        return a + b >= mod ? a + b - mod : a + b;
    }
    inline int Minus(const int &a, const int &b) {
        return a - b < 0 ? a - b + mod : a - b;
    }
    inline int Mul(const int &a, const int &b) {
        return 1ll * a * b % mod;
    }
    LL fpow(LL a, int b) {
        LL ans = 1;
        while(b) {
            if(b & 1) ans = ans * a % mod;
            a = a * a % mod, b >>= 1;
        }
        return ans;
    }
    struct NE {
        int r, i;
        NE operator + (const NE &A) const {
            return (NE) {Plus(r, A.r), Plus(i, A.i)};
        }
        NE operator * (const NE &A) const {
            return (NE) {Plus(Mul(r, A.r), Mul(Mul(A.i, i), w2)),
                         Plus(Mul(r, A.i), Mul(i, A.r))};
        }
    };
    NE fpow(NE a, int b) {
        NE ans = (NE) {1, 0};
        while(b) {
            if(b & 1) ans = ans * a;
            a = a * a, b >>= 1;
        }
        return ans;
    }
    int Sqroot(int n) {
        int a, ans;
        if(fpow(n, mod - 1 >> 1) != 1)
            return -1;
        do {
            a = Rand() % mod;
            w2 = Minus(Mul(a, a), n);
        } while(fpow(w2, mod - 1 >> 1) == 1);
        ans = fpow((NE) {a, 1}, mod + 1 >> 1).r;
        return min(ans, mod - ans);
    }
    map<int, int > mp;
    int log_x(int x, int a) {
        mp.clear();
        int mx = (int)ceil(sqrt(mod)), ans = inf;
        int x_m = fpow(x, mx), tmp = x_m;
        for(register int i = 1; i <= mx; ++i)
            mp[tmp] = i, tmp = Mul(tmp, x_m);
        tmp = a;
        for(register int i = 0; i <= mx; ++i) {
            if(mp[tmp]) ans = min(mp[tmp] * mx - i, ans);
            tmp = Mul(tmp, x);
        }
        return ans == inf ? -1 : ans;
    }
}
 
int main() {
    using namespace NT;
    int a, sqrt5, delta, ans = inf, x, inv2, t;
    scanf("%d", &a);
    sqrt5 = Sqroot(5);
    inv2 = fpow(2, mod - 2);
    //奇数情况
    delta = Minus(Mul(5, Mul(a, a)), 4);
    delta = Sqroot(delta);
    t = 1ll * (1 + sqrt5) * inv2 % mod;
    if(~delta) {
        x = Mul(Plus(Mul(sqrt5, a), delta), inv2);
        x = log_x(t, x);
        if(~x && x & 1) ans = min(ans, x);
        x = Mul(Minus(Mul(sqrt5, a), delta), inv2);
        x = log_x(t, x);
        if(~x && x & 1) ans = min(ans, x);
    }
    //偶数情况
    delta = Plus(Mul(5, Mul(a, a)), 4);
    delta = Sqroot(delta);
    t = 1ll * (1 + sqrt5) * inv2 % mod;
    if(~delta) {
        x = Mul(Plus(Mul(sqrt5, a), delta), inv2);
        x = log_x(t, x);
        if(~x && !(x & 1)) ans = min(ans, x);
        x = Mul(Minus(Mul(sqrt5, a), delta), inv2);
        x = log_x(t, x);
        if(~x && !(x & 1)) ans = min(ans, x);
    }
    printf("%d", ans == inf ? -1 : ans);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链