首页 > 代码库 > UVa 11582 (快速幂取模) Colossal Fibonacci Numbers!
UVa 11582 (快速幂取模) Colossal Fibonacci Numbers!
题意：
斐波那契数列f(0) = 0, f(1) = 1, f(n+2) = f(n+1) + f(n) (n ≥ 0)
输入a、b、n，求f(ab)%n
分析：
构造一个新数列F(i) = f(i) % n，则所求为F(ab)
如果新数列中相邻两项重复出现的话，则根据递推关系这个数列是循环的。
相邻两项所有可能组合最多就n2中，所以根据抽屉原理得到这个数列一定是循环的。
求出数列的周期，然后快速幂取模即可。
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 5 const int maxn = 1000 + 10; 6 typedef unsigned long long ULL; 7 int f[maxn][maxn * 6], period[maxn]; 8 9 int pow_mod(ULL a, ULL b, int n)10 {11 if(b == 0) return 1;12 int k = pow_mod(a, b/2, n);13 k = k * k % n;14 if(b % 2 == 1) k = k * a % n;15 return k;16 }17 18 int solve(ULL a, ULL b, int n)19 {20 if(a == 0 || n == 1) return 0;21 int p = pow_mod(a % period[n], b, period[n]);22 return f[n][p];23 }24 25 int main(void)26 {27 freopen("11582in.txt", "r", stdin);28 for(int n = 2; n < maxn; ++n)29 {30 f[n][0] = 0, f[n][1] = 1;31 for(int i = 2; ; ++i)32 {33 f[n][i] = (f[n][i-2] + f[n][i-1]) % n;34 if(f[n][i-1] == 0 && f[n][i] == 1)35 {36 period[n] = i - 1;37 break;38 }39 }40 }41 42 ULL a, b;43 int n, T;44 scanf("%d", &T);45 while(T--)46 {47 cin >> a >> b >> n;48 printf("%d\n", solve(a, b, n));49 }50 51 return 0;52 }
UVa 11582 (快速幂取模) Colossal Fibonacci Numbers!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。