## UVa #11582 Colossal Fibonacci Numbers! (例题10-1)

2018年10月13日 ⁄ 综合 ⁄ 共 808字 ⁄ 字号 评论关闭

Run Time: 0.072s

```#define UVa  "LT10-1.11582.cpp"		//Colossal Fibonacci Numbers!
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

//Global Variables. Reset upon Each Case!
typedef unsigned long long ULL;
const int maxn = 1000 + 5;
int m[maxn];
unsigned long long f[maxn][3100];
unsigned long long a,b;
int n;
/////

int power(ULL a, ULL b, int t) {
ULL result = 1;
while(b) {
if(b%2) {
result = (a*result)%t;
}
a = (a*a)%t;
b/=2;
}
return result;
}

int main() {
for(n = 2; n <= 1000; n ++) {
int tmp = 0;
f[n][0] = 0, f[n][1] = 1;
for(int i = 2; ; i ++) {
f[n][i] = (f[n][i-2]%n + f[n][i-1]%n) % n;
if(f[n][i] == 1 && f[n][i-1] == 0) {
m[n] = i-1;
break;
}
}
}

int T;
scanf("%d", &T);
while(T--) {
scanf("%llu%llu%d", &a, &b, &n);
if(a == 0 || n == 1) printf("0\n");
else printf("%d\n", f[n][power(a%m[n], b, m[n])]);
}

return 0;
}
```