UVA11582 求很大的斐波那契 快速幂膜

2019-04-13 20:33发布

站内文章 / 模拟电子
18056 0 1188
题意：让你求费伯纳西数列的第a的b次方项模n的结果。 由于是每一项都对n取模，所以不同的n值都会对应一个周期，只要循环一下。当前项等于f1，前一项等于f0时就可以跳出循环了。
a的b次方，可以用幂取模的知识，快速分治求出。
注意第二个样例a要先模一下周期，不然会有溢出。
刚开是long long 也会溢出，所以要用unsigned long long。 在%n意义下，斐波那契是会有循环节的，这个循环节是多少呢？因为只要有任意两个一样，那么后面一直累加出来的数列也是一样的，那就会出现一个循环节 #include #include #include #include #include #include #include using namespace std; typedef unsigned long long ULL; const int maxn = 1024; int f[maxn][maxn*6]; int g[maxn]; int qpow(ULL a, ULL b, int m) { int ret=1; while(b) { if(b & 1)ret*=a,ret%=m; a*=a;a%=m; b>>=1; } return ret; } int main() { for(int i = 2; i < maxn; i++) { f[i][0] = 0; f[i][1] = 1; for(int j = 2; ; j++) { f[i][j] = (f[i][j-1]+f[i][j-2])%i; if(f[i][j-1] == 0 && f[i][j] == 1) { g[i] = j-1; break; } } } int T, n; ULL a, b; scanf("%d", &T); while(T--) { cin >> a >> b >> n; if(a == 0 || n == 1) { printf("0 "); } else { int p = qpow(a%g[n], b, g[n]); printf("%d ", f[n][p]); } } return 0; }上面qpow是迭代的写法有一种递归写法 int pow_mod(ull a, ull b, int m) { if(b==0) return 1; int k=pow_mod(a, b/2, m); k=k*k%m; if(b%2) k=k*a%m; return k; }


热门文章