没错又是我，我的上一个帖子在这里： ？TLE？

这次我写了 $BSGS$，理论上来说复杂度是保持在 $O(sqrt(n))$ 不变的，但是我超时了，蒟蒻求助大佬帮忙看一下为什么啊 QAQ

代码：

/*
斐波那契数列的循环节的上界为 6p
设斐波那契的第 i 项和第 i + 1 项构成的矩阵为 Ai，转移矩阵为B。
如果有循环节 k，那么有 A1 * B ^ k = A1 mod p
B ^ k = I，I 表示单位矩阵，将问题转化为 BSGS 的标准形式

B ^ k = I，设 k = i * s - j，s = ceil(sqrt(mod))，i, j <= s
B ^ (i * s - j) = I
B ^ (i * s) = B ^ j
枚举 j，O(sqrt(mod))，映射 M[B ^ j] = j
枚举 i，O(sqrt(mod))，如果 M[B ^ (i * s)] != 0，循环节 = i * s - j
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <map>
#define int long long
using namespace std;
void write(__int128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x<10)
	{
		putchar(x+48);
		return;
	}
	write(x/10);
	putchar(x%10+48);
}
const int N = 30000010;

struct gjd
{
	int a[N], cnt;
	void scan()
	{
		char c;
		while (scanf("%c", &c) && ('0' <= c && c <= '9')) { a[++cnt] = c - '0'; }
		for (int i = 1; i <= cnt / 2; i++) swap(a[i], a[cnt - i + 1]);
	}
	int div(int x) /// 返回 a % x
	{
		for (int i = cnt; i >= 2; i--) { a[i - 1] += (a[i] % x) * 10; a[i] /= x; }
		return a[1] % x;
	}
} n;
int mod;

struct matrix
{
	int a[4][4];
	void clear() { memset(a, 0, sizeof(a)); }
	void fil(matrix* b)
	{
		clear();
		for (int i = 1; i <= 2; i++)
			for (int j = 1; j <= 2; j++) a[i][j] = b->a[i][j];
	}
	void mul(matrix* b)
	{
		int tmp[4][4]; memset(tmp, 0, sizeof(tmp));
		for (int i = 1; i <= 2; i++)
			for (int j = 1; j <= 2; j++)
				for (int k = 1; k <= 2; k++)
				{
					tmp[i][j] += a[i][k] * b->a[k][j];
					tmp[i][j] %= mod;
				}
		for (int i = 1; i <= 2; i++)
			for (int j = 1; j <= 2; j++) a[i][j] = tmp[i][j];
	}
	void pow(matrix* b, int p) /// a = b ^ p
	{
		memset(a, 0, sizeof(a)); a[1][1] = a[2][2] = 1;
		matrix base; base.fil(b);
		while (p)
		{
			if (p & 1) mul(&base);
			matrix tmp; tmp.fil(&base); base.mul(&tmp); p >>= 1;
		}
	}
	__int128 tranverse()
	{
		__int128 ret = 0, base = 1e10;
    /// 对于 a[][]，如果 a[][] = base，a[1][2] = a[2][1]，压缩时减去一维
		ret = ret * base + (__int128) a[1][1];
		ret = ret * base + (__int128) a[2][1];
		ret = ret * base + (__int128) a[2][2];
		return ret;
	}
	void print()
	{
	    for (int i = 1; i <= 2; i++)
	    {
			for (int j = 1; j <= 2; j++) printf("%lld ", a[i][j]);
			printf("\n");
	    }
	}
} base, I; /// 转移矩阵 (在 BSGS 函数中不改变)，单位矩阵

int get(int x) /// 获取 f[x]
{
	matrix ret; ret.fil(&I); ret.pow(&base, x - 1);
	return (ret.a[1][1] + ret.a[2][1]) % mod;
}

map<__int128, int> M; /// mp[k] 表示矩阵为 k 的 j = 多少
int s; /// i * s - j
int len; /// 循环节长度

void BSGS()
{
	M[I.tranverse()] = 0; /// j = 0，j 可以 = 0，i 不行
	matrix tmp; tmp.fil(&I); /// M[tmp]
	for (int j = 1; j < s; j++) /// M[base ^ j] = j，j 不能 = s
	{
		tmp.mul(&base);
		M[tmp.tranverse()] = j;
	}
	
	tmp.fil(&I);
	matrix tmp2; tmp2.pow(&base, s); /// tmp2 = base ^ s
	for (int i = 1; i <= s; i++) /// M[base ^ (i * s)]
	{
		tmp.mul(&tmp2); int j = M[tmp.tranverse()];
		if (j != 0) { len = i * s - j; break; }
	}
}


signed main()
{
	n.scan(); scanf("%lld", &mod); s = ceil(sqrt(8 * mod)); /// 循环节上界是 6 * mod
	base.a[1][1] = 0; base.a[1][2] = 1;
	base.a[2][1] = 1; base.a[2][2] = 1;
	I.a[1][1] = 1; I.a[2][2] = 1;
	BSGS();
	int fn = n.div(len);
	int res = get(fn); printf("%lld", res);
	return 0;
}

得了 83 分捏