题意：求ceil（(a+√b)ⁿ）%m，0< a, m < 2¹⁵, (a-1)²< b < a², 0 < b, n < 2³¹。

思路：若(a+√b)ⁿ == x + y·√b（x、y为整数），则(a－√b)ⁿ == x － y·√b。又因为a－1 < √b < a，所以0 < (a－√b)ⁿ < 1，即x－1 < y·√b < x，所以ceil（(a+√b)ⁿ） == 2x。接下来事情就容易多了，同时对x、y两部分进行快速幂取模即可，证明略。

1 #include 
     
       2 typedef long long llg; 3 llg a,b,n,m; 4 void solve(){ 5     llg ans1(1),ans2(0),t1(a),t2(1); 6     llg tmp; 7     while(n){ 8         if(n&1){ 9             tmp = ans1;10             ans1 = (ans1*t1+ans2*t2*b)%m;11             ans2 = (tmp*t2+ans2*t1)%m;12         }13         tmp = t1;14         t1 = (t1*t1+t2*t2*b)%m;15         t2 = 2*tmp*t2%m;16         n >>= 1;17     }18     printf("%lld\n",ans1*2%m);19 }20 int main(){21     while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&m))22         solve();23     return 0;24 }