[C++知识库]CF193E Fibonacci Number

https://www.luogu.com.cn/problem/CF193E

属实是知识盲区了

通过打表不难发现在
膜$10^4$下循环节是$1.5\times 10^4$
膜$10^5$下循环节是$1.5\times 10^5$
膜$10^6$下循环节是$1.5\times 10^6$
膜$10^7$下循环节是$1.5\times 10^7$

以此类推类推，后面$\mathrm{m}\mathrm{o}\mathrm{d}10^i$循环节是$1.5\times 10^i$

这相当于是保留了后$i$位

容易得到
如果$fib(x)\mathrm{m}\mathrm{o}\mathrm{d}10^i=n\mathrm{m}\mathrm{o}\mathrm{d}10^i$
一定是由$\mathrm{m}\mathrm{o}\mathrm{d}10^{i?1}$相等的那批加上$k\times$循环节长度得到的

于是可以先处理$10^5$以内的，然后往后推即可

code:

#include<bits/stdc++.h>
#define N 2000050
#define ll long long
using namespace std;
ll mod;
// ll mul(ll a, ll b) {
//     ll d = (long double) a / mod * b + 0.5;
//     ll r = a * b - d * mod;
//     return r < 0 ? r + mod : r;
// }
ll mul(ll x, ll y) {
    ll ret = 0; 
    for(; y; y >>= 1ll) {
        if(y & 1) ret = (ret + x) % mod;
        x = (x + x) % mod;
       // printf("%lld %lld\n", x, y);
    }
    //printf("%lld %lld %lld\n", x, y, ret);
    return ret;
}
struct MT {
    ll a[2][2];
    void init() {
        for(int i = 0; i < 2; i ++)
            for(int j = 0; j < 2; j ++) a[i][j] = (i == j);
    }
    MT operator * (const MT& o) const {
        MT c;
        for(int i = 0; i < 2; i ++)
            for(int j = 0; j < 2; j ++) {
                c.a[i][j] = 0;
                for(int  k = 0; k < 2; k ++) 
                    c.a[i][j] = (c.a[i][j] + mul(a[i][k], o.a[k][j]) ) % mod;
            }
        return c;
    }
};
MT qpow(MT x, ll y) {
    MT ret; ret.init(); //ll ha = y;
    //printf("qpow %lld\n", y);
    for(; y; y >>= 1, x = x * x) {
	//	if(ha == 1500000006ll) printf("*%lld*", y);
    	if(y & 1ll) ret = ret * x;
	}
    return ret;
}
ll fib(ll n) { //printf("** %lld\n", n);
    
    if(!n) return 0;
    MT a;
    a.a[0][0] = 0, a.a[0][1] = a.a[1][0] = a.a[1][1] = 1;
	
    a = qpow(a, n - 1);
   // printf("end\n");
    return a.a[1][1];
}  
ll n, a[N], ls[N], f[N];
int gs, vis[N];
int main() {
  //  freopen("b.out","w",stdout);
    scanf("%lld", &n);
    if(!n) {
        printf("0");
        return 0;
    }
    if(n == 1) {
        printf("1");
        return 0;
    }
    mod = 100000;
    f[0] = 0, f[1] = 1;
    if(f[0] % mod == n % mod) a[++ gs] = 0;
    if(f[1] % mod == n % mod) a[++ gs] = 1;
    for(int i = 2; ; i ++) {
        f[i] = (f[i - 1] + f[i - 2]) % mod;
        if(f[i] == 1 && f[i - 1] == 0) break;
        if(f[i] % mod == n % mod) a[++ gs] = i;
    }
    //for(int i = 1; i <= gs; i ++) printf("%lld ", a[i]); printf("\n");
    ll xhj = 150000;
    for(mod = mod * 10; mod <= 10000000000000ll; mod = mod * 10, xhj = xhj * 10) {
        int sz = 0;
         for(int i = 1; i <= gs; i ++) {
             for(int j = 0; j <= 9; j ++) {
                 if(fib(a[i] + j * xhj) == n % mod) {
                     ls[++ sz] = a[i] + j * xhj;
                 }
             }
         }
        gs = sz;
        for(int i = 1; i <= gs; i ++) a[i] = ls[i];
      //  for(int i = 1; i <= gs; i ++) printf("%lld ", a[i]); printf("     %lld\n", mod);
    }
    if(!gs) {
        printf("-1");
        return 0;
    }
    sort(a + 1, a + 1 + gs);
    printf("%lld", a[1]);
    return 0;
}