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

2019-04-14 16:51发布

站内文章 / 模拟电子
14454 0 1447
预处理求出n分别为1-1000时斐波那契模数列的周期，之后求出a^b是周期中第几个即可。
复习了模算术、幂取模，顺便学习了分治法取模的迭代版本。

Run Time: 0.072s #define UVa "LT10-1.11582.cpp" //Colossal Fibonacci Numbers! char fileIn[30] = UVa, fileOut[30] = UVa; #include #include #include 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 "); else printf("%d ", f[n][power(a%m[n], b, m[n])]); } return 0; }

热门文章