题目：In the math class, the evil teacher gave you one unprecedented problem! 

Here f(n) is the n-th fibonacci number (n >= 0)! Where f(0) = f(1) = 1 and for any n > 1, f(n) = f(n - 1) + f(n - 2). For example, f(2) = 2, f(3) = 3, f(4) = 5 ... 

The teacher used to let you calculate f(n) mod p where n <= 10^18 and p <= 10^9, however , as an ACMER, you may just kill it in seconds! The evil teacher is mad about this. Now he let you find the smallest integer m (m > 0) such that for ANY non-negative integer n ,f(n) = f(n + m) (mod p) . For example, if p = 2, then we could find know m = 3 , f(0) = f(3) = 1(mod 2), f(1) = f(4) (mod 2) .... 

Now the evil teacher will only give you one integer p( p <= 2* 10^9), will you tell him the smallest m you can find ?InputThe first line is one integer T indicates the number of the test cases. (T <=20) 

Then for every case, only one integer P . (1 <= P <= 2 * 10^9, the max prime factor for P is no larger than 10^6)OutputOutput one line. 

First output “Case #idx: ”, here idx is the case number count from 1.Then output the smallest m you can find. You can assume that the m is always smaller than 2^64 .Sample Input5 11 19 61 17 67890Sample OutputCase #1: 10 Case #2: 18 Case #3: 60 Case #4: 36 Case #5: 4440
代码：#include using namespace std; #define ll long long int fb[2000000]; int list[1000001], p[78498];//78497个素数 void getp()//在p数组中存所有不超过1000000的素数 { p[0] = 2; int key = 0; for (int i = 0; i <= 1000000; i++)list[i] = i % 2; for (int i = 3; i <= 1000000; i += 2)if (list[i]) { p[++key] = i; for (int j = i + i; j <= 1000000; j += i)list[j] = 0; } } ll gcd(ll a, ll b) { if (b)return gcd(b, a%b); return a; } ll lcm(ll a, ll b) { return a / gcd(a, b)*b; } ll fp(int n)//n是素数 { fb[0] = 0, fb[1] = 1; for (int i = 2;; i++) { fb[i] = (fb[i - 1] + fb[i - 2]) % n; if (fb[i - 1] == 1 && fb[i] == 0)return i; } return 0; } ll f2(ll n) { ll ans = 1, m; int a; for (int i = 0; i < 78497; i++) { a = p[i]; if (n%a)continue; m = 1; while (n%a == 0)m *= a, n /= a; ans = lcm(ans, m / a * fp(a)); } return ans; } int main() { getp(); int T; cin >> T; ll n; for (int i = 1; i <= T; i++) { cin >> n; cout << "Case #" << i << ": " << f2(n) << endl; } return 0; }
理论基础：

解题思路：把n因式分解成各个素数的幂，为了完成因式分解要预先把所有可能的素数都计算出来存到一个数组里面，这部分代码和POJ - 2689 Prime Distance（2次用筛法）这里面是一样的求出斐波那契数列模各个素数幂的周期，所有周期的最小公倍数就是答案。要想求出斐波那契数列模素数幂的周期，只需要求出模这个素数的周期。根据素数的大小和上面的理论进行计算发现，斐波那契数列模素数的周期不会超过2*10^6，所以可以直接暴力求取。