Colossal Fibonacci Numbers! UVA

Colossal Fibonacci Numbers! UVA

题意

紫书第十章的题目。多组数据，每次给出三个数a,b,n，（a,b< 2 64 2^{64} 264，n<=1000），问第 a b a^{b} ab个斐波那契数模n的值。斐波那契数列从f(0)=0,f(1)=1开始。

题解

因为是要求出 f ( a b ) f(a^{b}) f(ab)%n的值，所以先在%n条件下算出斐波那契数列。算到哪里结束呢？注意到在%n条件下，斐波那契数列如果前两个数相同，则由递推公式 f ( i ) = f ( i − 1 ) + f ( i − 2 ) f(i)=f(i-1)+f(i-2) f(i)=f(i−1)+f(i−2)，第三个数也相同，同理后面的数列都相同，是周期性的循环。而%n下最多只有 n 2 n^{2} n2个不同的数对，所以在 n 2 n^{2} n2+2范围内一定会出现重复的数对，所以最多只需要算出0~ n 2 + 2 n^{2}+2 n2+2的斐波那契数列。
而且循环节一定包含f(0),f(1)。可以反证法证明：假设循环节不包含f(0),f(1)，不妨假设循环节从f(i), i>=2开始，循环长度为t,即 f ( i ) = f ( i + t ) f(i)=f(i+t) f(i)=f(i+t), f ( i + 1 ) = f ( i + 1 + t ) f(i+1)=f(i+1+t) f(i+1)=f(i+1+t), i > = 2 i>=2 i>=2。则 f ( i − 1 ) = f ( i + 1 ) − f ( i ) = f ( i + 1 + t ) − f ( i + t ) = f ( i − 1 + t ) f(i-1)=f(i+1)-f(i)=f(i+1+t)-f(i+t)=f(i-1+t) f(i−1)=f(i+1)−f(i)=f(i+1+t)−f(i+t)=f(i−1+t) ( m o d n ) (mod n) (modn)即循环节从 f ( i − 1 ) f(i-1) f(i−1)开始，与假设矛盾。简单的说就是如果这个斐波那契数列的第i,i+1个值和第i+t,i+1+t的值分别相等，则它们前面的数列也相等（由递推式移项可得），就能一直往前推到f(0)=f(t),f(1)=f(t+1)。
所以直接从i=2开始找，第一个使得f(i)=f(0),f(i+1)=f(1)的i就是循环周期T。用快速幂算出pos= a b a^{b} ab%T后输出f(pos)即可。
注意a,b的范围是< 2 64 2^{64} 264，所以要用unsigned long long。
特判当n=1时，直接输出0即可。

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mxn=1000010;ull a,b,n;
int fi[mxn];int ksm(ull a,ull b,ull mod)
{ull ret=1,tmp=a;while(b){if(b&1) ret=(ret*tmp)%mod;tmp=(tmp*tmp)%mod;b>>=1;}if(ret<0) ret+=mod;return ret;
}int main()
{int kase;cin>>kase;while(kase--){cin>>a>>b>>n;if(n==1) {cout<<0<<endl;continue;}ll bis=n*n+2;ll t;fi[0]=0,fi[1]=1;for(int i=2;i<=bis;i++){fi[i]=(fi[i-1]+fi[i-2])%n;if(fi[i-1]==0&&fi[i]==1){t=i-1;break;}}int pos=ksm(a%t,b,t);cout<<fi[pos]<<endl;}return 0;
}