公式推导: ( a + b ^ 0.5 ) ^ n + ( a - b ^ 0.5 ) ^ n = Ck, Ck * ( ( a + b ^ 0.5 ) + ( a - b ^ 0.5 ) ) = ( ( a + b ^ 0.5 ) + ( a - b ^ 0.5 ) ) * ( a + b ^ 0.5 ) ^ n + ( a - b ^ 0.5 ) ^ n => 2 * a * Ck = Ck+1 + (a * a - b) * Ck-1 => Ck+1 + Ck = Ck * (2 * a + 1 ) + (a * a - b) * Ck-1 ==> Ck + 1 = 2 * a b - a * a * Ck Ck 1 0 Ck -1 ==> Ck + 1 = 2 * a b - a * a ^ n * 2 * a Ck 1 0 2 //#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #define LL long long LL s[2], m; struct node { LL arr[2][2]; }; node power(node p, int pos){ if(pos == 1) return p; node v = power(p, pos / 2); node q; q.arr[0][0] = (v.arr[0][0] * v.arr[0][0] + v.arr[0][1] * v.arr[1][0]) % m; q.arr[0][1] = (v.arr[0][0] * v.arr[0][1] + v.arr[0][1] * v.arr[1][1]) % m; q.arr[1][0] = (v.arr[1][0] * v.arr[0][0] + v.arr[1][1] * v.arr[1][0]) % m; q.arr[1][1] = (v.arr[1][0] * v.arr[0][1] + v.arr[1][1] * v.arr[1][1]) % m; if(pos % 2 == 0) return q; v.arr[0][0] = (q.arr[0][0] * p.arr[0][0] + q.arr[0][1] * p.arr[1][0]) % m; v.arr[0][1] = (q.arr[0][0] * p.arr[0][1] + q.arr[0][1] * p.arr[1][1]) % m; v.arr[1][0] = (q.arr[1][0] * p.arr[0][0] + q.arr[1][1] * p.arr[1][0]) % m; v.arr[1][1] = (q.arr[1][0] * p.arr[0][1] + q.arr[1][1] * p.arr[1][1]) % m; return v; } int main() { // freopen("in.txt", "r", stdin); LL a, b; int n; while (scanf("%I64d %I64d %d %I64d", &a, &b, &n, &m) != EOF){ if(n == 1){ printf("%lld\n", a * 2 % m); continue; } s[0] = 2 * a % m, s[1] = 2; node p; p.arr[0][0] = a * 2 % m; p.arr[0][1] = (b - a * a) % m; p.arr[1][0] = 1, p.arr[1][1] = 0; node q = p; q = power(p, n - 1); printf("%I64d\n", (q.arr[0][0] * s[0] % m + q.arr[0][1] * s[1] % m + m * 2) % m); } return 0; }