- [Fib数模n的循环节](https://blog.csdn.net/acdreamers/article/details/10983813);
- [The Period of the Fibonacci Sequence Modulo j](http://gradprogram.math.arizona.edu/~ura-reports/071/Campbell.Charles/Final.pdf).
证明过于复杂, 因此题解中没人讲到.
在我的代码中, 这部分的代码
```c++
namespace {
long long Fac[N]; int cnt;
long long Judge (long long k, long long p) {
cnt = 0;
for (long long i = 1; i * i <= k; i += 1){
if (k % i) continue;
Fac[cnt ++] = i;
if (i * i < k) Fac[cnt ++] = k / i;
}//Fac为k的所有因子
std:: sort (Fac, Fac + cnt);
for (int i = 0; i < cnt; i += 1)
if (Fib(Fac[i] + 5, p) == 5) // 判断Fac[i]是不是所求的M
// 这里实际上是判断 Fib(Fac[i]+5) 是否等于 Fib(5),可以把5换成其它.
return Fac[i];
}
const long long Rest[6] = {0, 1, 3, 8, 6, 20};
long long g (long long p) {
if (p <= 5) return Rest[p];
if (Pow(5, (p - 1) >> 1, p) == 1)
return Judge (p-1, p);
else return Judge ((p + 1) << 1, p);
}
long long Get (long long p) {
PrimeGenerate (); //生成1e5以内的质数
long long tmp, pre;
long long lcm = 1ll;
for (int i = 1; i <= tot && pri[i] * pri[i] <= p; i += 1) {
if (p % pri[i]) continue; pre = p / pri[i];
while (p % pri[i] == 0) p /= pri[i];
tmp = g (pri[i]) * (pre / p), lcm = lcm / gcd (lcm, tmp) * tmp;
}
if (p > 1) {
tmp = g(p);
lcm = lcm * tmp / gcd(lcm, tmp);
}
return lcm;
}
} // Get the Mod Sum;
```
利用矩阵快速幂求斐波那契数列相信大家都会
```c++
namespace {
long long mod;// 模数
struct Matrix {
int r, c;
long long m[3][3];
inline Matrix () { memset(m, false, sizeof m); }
inline Matrix (int n, int m) :Matrix() { r = n, c = m; }
inline Matrix (int n) :Matrix() { r = c = n; m[0][0] = m[1][1] = 1ll; }
inline Matrix operator * (const Matrix &o) const {
Matrix res = Matrix (r, o.c);
for (int i = 0; i < r; i += 1)
for (int j = 0; j < o.c; j += 1)
for (int k = 0; k < c; k += 1)
res.m[i][j] += 1ll * m[i][k] * o.m[k][j] % mod,
res.m[i][j] %= mod;
return res;
}
Matrix operator ^ (long long o) const {
Matrix base = *this;
Matrix resl = Matrix (r);
while (o) {
if (o & 1ll)
resl = resl * base;
base = base * base;
o >>= 1;
}
return resl;
}
};
long long Fib (long long n, long long Mod) {
if (n == 0) return 0ll;
if (n == 1 || n == 2) return 1ll;
mod = Mod; n -= 1;
Matrix a = Matrix (2, 1);
a.m[0][0] = 1;
Matrix b = Matrix (2, 2);
b.m[0][0] = b.m[1][0] = b.m[0][1] = 1;
a = (b ^ n) * a;
return a.m[0][0];
}
} //Get The Fibnacci Sequence !
```
以及将读入的那个三百万位的整数进行取模
```c++
namespace {
char ch[N*300];
void Read() { scanf("%s", ch); }
long long Int(long long p) {
register long long res = 0;
register int pos = 0;
while (!isdigit(ch[pos])) pos += 1;
while (isdigit(ch[pos]))
res = res * 10 + ch[pos] - '0', res %= p, pos += 1;
return res;
}
}// Big Integer
```
这部分是效率瓶颈, ~~不要妄想用`cin`来读入.~~
### Code
[完整代码](https://paste.ubuntu.com/p/m5SV5QSZxN/)