UVa11582
Colossal Fibonacci Numbers!
Oooh...pretty
The i’th Fibonacci number f(i) is recursively
defined in the following way:
• f(0) = 0 and f(1) = 1
• f(i + 2) = f(i + 1) + f(i) for every
i 0
Your task is to compute some values
of this sequence.
Input
Input begins with an integer t 10; 000,
the number of test cases. Each test case
consists of three integers a, b, n where
0 a; b < 264 (a and b will not both be
zero) and 1 n 1000.
Output
For each test case, output a single line containing the remainder of f(ab) upon division by n.
Sample Input
31
1 2
2 3 1000
18446744073709551615 18446744073709551615 1000
Sample Output
1
21
250
题意：
给出64位整数a、b以及不超过1000的正整数n，求斐波那契数列第a ^ b项模n的结果。
输入：
情况数T，之后T行每行a、b、n。
输出：
斐波那契数列第a ^ b项模n的结果。
分析：
由于斐波那契数列的每一项都是由前两项相加得来，并且每一项都对n取模，所有每一项的情况一共有n种，而相邻两项若组成有序数对，则不同的数对的情况也只有n ^ 2种，所以只需要计算n * n项就可以找到数列规律。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 typedef unsigned long long ull; 6 const int maxn = 1000; 7 ull F[maxn * maxn + 10]; 8 int power(ull a,ull b,int t){ 9 ull res = 1; 10 while(b){ 11 if(b & 1) res = (a * res) % t; 12 a = (a * a) % t; 13 b >>= 1; 14 } 15 return res; 16 } 17 int main() 18 { 19 int T; 20 cin >> T; 21 while(T--) 22 { 23 ull a,b,n,l; 24 int flag = 1; 25 cin >> a >> b >> n; 26 if(n == 1) {printf("0 "); continue;} 27 F[0] = 0; 28 F[1] = 1; 29 for(ull i = 2 ; ; i++){ 30 F[i] = (F[i - 1] % n + F[i - 2] % n) % n; 31 if(F[i] == F[1] && F[i - 1] == F[0]){ 32 l = i - 1; 33 break; 34 } 35 } 36 cout << F[power(a % l, b, l)] << endl; 37 } 38 return 0; 39 }