UVA 11582 Colossal Fibonacci Numbers!

2019-04-14 20:26发布

站内文章 / 模拟电子
13407 0 1408
题目链接  http://acm.hust.edu.cn/vjudge/problem/41990
题意：让你求斐波纳契数列的第 a^b项 模n的结果(1<=n<=1000) 

预处理求出n分别为1-1000时斐波那契模数列的周期，不同的n值都会对应一个周期
之后求出a^b是周期中第几个
longlong会爆  要用unsigned longlon
#include #include #include #include #include #include #include #include #include #include #define pi acos(-1) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f using namespace std; typedef pair P; const int maxn = 1e5 + 5; vectorfib[1005]; int qpow(ULL x, ULL n, int mod) { int res = 1; while (n){ if (n & 1) res = (int)(res * x % mod); x = x * x % mod; n >>= 1; } return res; } void pre_process() { for (int m = 2; m <= 1000; m++){ fib[m].push_back(0); fib[m].push_back(1); for (int i = 2; ; i++){ fib[m].push_back( (fib[m][i-1] + fib[m][i-2]) % m ); if (fib[m][i] == 1 && fib[m][i-1] == 0) break; } int cnt = fib[m].size(); //多了1和0两个数 fib[m].resize(cnt-2); } } int main(void) { // freopen("C:\Users\wave\Desktop\NULL.exe\NULL\in.txt","r", stdin); ULL a, b; int n, T, dex; pre_process(); cin >> T; while(T--) { scanf("%llu %llu %d", &a, &b, &n); if (a == 0 || n == 1) printf("0 "); else { int mod = fib[n].size(); dex = qpow(a%mod, b, mod); // a要先mod一下 不然会爆 printf("%d ", fib[n][dex]); } } return 0; }

热门文章