题目抽象：y = (5 + 2 √6)^(1 + 2 ^ x). 给出整数x和m.求 [y] % m的值。 integer x (0≤x<2^32) . (M≤46337)
题目分析：指数超级大。模很小。对于一个给定的m。 当x变化时会出现循环节。
这个题目一个难点就是要向下取整求余。本题是向下取整，也就是向上取整加一。
还有就是指数太大，要找到循环节，其实由于mod小，循环节并没有太大，暴力跑就ok啦！ 参考博客
比赛的时候想不到找循环节。思维能力问题。
1 #include <cstdio> 2 using namespace std; 3 typedef long long LL; 4 5 const LL maxn = 47000; 6 LL r[maxn], ans[maxn], x, m; 7 8 LL Pow(LL a, LL n, LL mod) 9 { 10 LL res = 1; 11 while (n) 12 { 13 if (n % 2) 14 res = (res * a) % mod; 15 a = (a * a) % mod; 16 n >>= 1; 17 } 18 return res; 19 } 20 21 void init() 22 { 23 ans[0] = 2; 24 ans[1] = 10; 25 for (int i = 2; i<maxn; i++) 26 { 27 ans[i] = (10 * ans[i - 1] - ans[i - 2] + m) % m; 28 if (ans[i - 1] == ans[0] && ans[i] == ans[1]) 29 { 30 r[m] = i - 1; 31 return; 32 } 33 } 34 } 35 36 LL solve() 37 { 38 init(); 39 LL k = (1 + Pow(2, x, r[m])) % r[m]; 40 return (ans[k] - 1 + m) % m; 41 } 42 43 int main() 44 { 45 LL t; 46 scanf("%lld", &t); 47 for (int i = 1; i <= t; i++) 48 { 49 scanf("%lld %lld", &x, &m); 50 printf("Case #%d: %lld\n", i, solve()); 51 } 52 return 0; 53 }
原文：http://www.cnblogs.com/hutaishi/p/4830494.html