\(F_i,F_{i+1}\) を \(P\) で割った余りを考えます。 この余りの組として考えられるものは高々 \((P-1)^2\) 個で、かつ \(F_{i+2}\) を \(P\) で割った余りは \(F_i,F_{i+1}\) を \(P\) で割った余りから一意に定まるので、鳩ノ巣原理より、およそ \(P^2\) 個程度調べれば十分であることがわかります。

今回の問題では \(P\leq 3000\) と十分に \(P\) が小さいので、\(P^2\) 個程度調べれば間に合います。

なお、フィボナッチ数列での余りの周期が \(O(P\log P)\) で抑えられることが簡単に証明できるので、この問題は \(1\leq P\leq 2\cdot 10^5\) というような制約でも解くことができます。

想定解コードは以下の通りです。

#include <iostream>
#include <vector>
#define REP(i, n) for (int i = 1; i <= int(n); i++)
int main() {
	int P;
	std::cin >> P;
	std::vector<int> fib = {0, 1};
	for (int i = 2; i < P * P + 2; i++)
		fib.push_back((fib[i - 1] + fib[i - 2]) % P);
	REP(i, P * P + 2) {
		if (fib[i] % P == 0) {
			std::cout << i << std::endl;
			return 0;
		}
	}
	std::cout << -1 << std::endl;
}