题目概述

求最小的 $n$ 使得 $fib_n\equiv C(mod\ P)$ 。

解题报告

模板题调这么久我是不是没救了……题目要求：

$$ {1\over\sqrt5}[({1+\sqrt5\over 2})^n-({1-\sqrt5\over 2})^n]\equiv C(mod\ P) $$

令 $\alpha={1+\sqrt5\over 2}$ ，那么：

$$ \alpha^n-(-{1\over\alpha})^n\equiv\sqrt5C(mod\ P)\\ \alpha^{2n}-\sqrt5C\alpha^n-(-1)^n\equiv0(mod\ P)\\ \alpha^n\equiv{\sqrt5C\pm\sqrt{5C^2+4(-1)^n}\over 2} $$

先讨论 $n$ 的正负，算出 $\sqrt5,\sqrt{5C^2+4(-1)^n}$ ，再BSGS。

模意义下开根？Cipolla什么的好大啊，我们来BSGS吧！

求解：$x^2\equiv a(mod\ P)$ ，两边开根 $2logx=loga(mod\ P)\Rightarrow logx={loga\over 2}(mod\ P)$ 。

所以我们先算出 $P$ 的原根，然后BSGS算出 $g^k\equiv a(mod\ P)$ 的 $k$ ，那么 $x\equiv g^{k\over 2}(mod\ P)$ 。

注意特判 $a=0$ 。

示例程序

#include<cmath>
#include<cstdio>
#include<unordered_map>
typedef long long LL;
using namespace std;
const int maxs=44722;

int p[maxs+5];bool pri[maxs+5];
int te,C,MOD,g,INV2,SQR5,AL;unordered_map<int,int> f[2];

inline void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) break;}
    }
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline int getg(int MOD){
    for (int i=1;;i++){
        for (int j=1;j<=p[0]&&(LL)p[j]*p[j]<=MOD;j++)
            if (!((MOD-1)%p[j])) if (Pow(i,(MOD-1)/p[j])==1) goto END;
        return i;END:continue;
    }return -1;
}
inline int BSGS(int A,int B,int d=-1){
    f[0].clear();f[1].clear();int S=sqrt(MOD)+1,INV=Pow(A,MOD-2),blk=Pow(A,S);
    for (int i=0,pw=B;i<S;i++,pw=(LL)pw*INV%MOD) if (!f[i&1].count(pw)) f[i&1][pw]=i;
    for (int i=0,pw=1,now=MOD;i<S;i++,pw=(LL)pw*blk%MOD,now=MOD){
        if (d!=0&&f[i*S&1^1].count(pw)) now=min(now,f[i*S&1^1][pw]+i*S);
        if (d!=1&&f[i*S&1].count(pw)) now=min(now,f[i*S&1][pw]+i*S);if (now<MOD) return now;
    }return -1;
}
inline int Sqrt(int a) {if (!a) return 0;int k=BSGS(g,a);return k<0||(k&1)?-1:Pow(g,k>>1);}
inline int Solve(int d){
    int S=(d?Sqrt(((LL)C*C+MOD-4)%MOD):Sqrt(((LL)C*C+4)%MOD));if (S<0) return -1;
    int A=BSGS(AL,(LL)(C+S)*INV2%MOD,d),B=BSGS(AL,(LL)(C+MOD-S)*INV2%MOD,d);
    if (A<0) A=B;if (~B) A=min(A,B);return A;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(maxs),scanf("%d",&te);te;te--){
        scanf("%d%d",&C,&MOD);g=getg(MOD);INV2=MOD+1>>1;SQR5=Sqrt(5);AL=(LL)(SQR5+1)*INV2%MOD;
        C=(LL)C*SQR5%MOD;int A=Solve(0),B=Solve(1);if (A<0) A=B;if (~B) A=min(A,B);printf("%d\n",A);
    }return 0;
}