2015
04-14

# Evil teacher

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 ?

The 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)

The 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)

5
11
19
61
17
67890

Case #1: 10
Case #2: 18
Case #3: 60
Case #4: 36
Case #5: 4440

a，2a，3a，5a，8a，….。可以看出a的系数就是一个fib数列，那么我们就可以得到fib(k+i)%p=a*fib(i)%p，其中i满

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 1000005
bool isprime[maxn];
typedef long long ll;
ll prime[maxn],nprime;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
void getprime()
{
ll i,j;
memset(isprime,1,sizeof(isprime));
nprime=0;
for(i=2; i<maxn; i++)
if(isprime[i])
{
prime[nprime++]=i;
for(j=i*i; j<maxn; j+=i) isprime[j]=0;
}
}
ll factor[100][2],tol;
void findfac(ll n)
{
ll x=n,l=(ll)sqrt((double)n);
tol=0,memset(factor,0,sizeof(factor));
for(int i=0; prime[i]<=l; i++)
if(x%prime[i]==0)
{
factor[tol][0]=prime[i];
while(x%prime[i]==0) factor[tol][1]++,x/=prime[i];
tol++;
}
if(x>1) factor[tol][0]=x,factor[tol++][1]++;
}
ll exp_mod(ll a,ll b,ll c)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%c;
b>>=1,a=a*a%c;
}
return ret;
}
ll getPrimeLoop(ll p)//求一个素数的循环节
{
ll pos=3,f1=1,f2=1,f3=2%p,k=1e9,l=(ll)sqrt((double)p-1);
while(f3) f1=f2,f2=f3,f3=(f1+f2)%p,pos++;//找到第一个值是0的点
for(ll i=1; i<=l; i++)
if((p-1)%i==0)
{
if(exp_mod(f2,(p-1)/i,p)==1) k=min(k,(p-1)/i);
if(exp_mod(f2,i,p)==1) k=min(k,i);
}
return pos*k;
}
ll solve(ll p,ll k)//求一个素数的k次方的循环节
{
ll ans=getPrimeLoop(p);
for(int i=0; i<k-1; i++) ans*=p;
return ans;
}
int main()
{
int t,ca=0;
ll n,ans;
getprime();
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
findfac(n);
ans=1;
ll temp;
for(int i=0; i<tol; i++)
temp=solve(factor[i][0],factor[i][1]),ans=ans/gcd(ans,temp)*temp;
printf("Case #%d: %I64d\n",++ca,ans);
}
return 0;
}