cf 981 F.Kosuke's Sloth
F. Kosuke's Sloth
思路
由皮亚诺定理可知，模数为\(k\)的循环节长度不会超过\(6k\)，所以我们可以暴力枚举找到第一个\(k\)的倍数的位置\(p\),答案即为\(pn\)，时间复杂度复杂度\(O(m)\)
相关证明：
Pisano Period - Shiina_Mashiro - 博客园
推论：
斐波那契数列取余是否有规律？ - 知乎
代码
void solve()
{
ll n;
cin >> n;
int m;
cin >> m;
f[1] = 1;
f[2] = 1;
ll p = 0;
int i = 3;
while (1)
{
f[i] = (f[i - 1] + f[i - 2]) % m;
if (!f[i])
{
p = i;
break;
}
i++;
}
if (m == 1)
p = 1;
cout << (n % mod) * (p % mod) % mod << "\n";
}
原文参考