ほとんど同じ問題を考えたことがあったので割りと一瞬でした。
解法
X = (A*X + B) mod C
というのは, 行列計算で言うと mat[0][0] = A, mat[0][1] = B, mat[1][0] = 0, mat[1][1] = 1 というのを使って
mat * x (x は第一成分が X, 第二成分が 1) と表せます。
これで j のループは O(1) の行列計算で出来るようになったので, 単純に足し算していけば答えが得られます。
typedef long long number; typedef vector<number> vec; typedef vector<vec> matrix; ll MOD = 1e9+7; matrix identity(int n) { matrix A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n^3 ) matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), vec(B[0].size())); for (int i = 0; i < (int)C.size(); ++i) for (int j = 0; j < (int)C[i].size(); ++j) for (int k = 0; k < (int)A[i].size(); ++k) { C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } return C; } // O( n^3 log e ) matrix pow(const matrix &A, ll e) { if (e == 0) return identity(A.size()); if (e == 1) return A; if (e % 2 == 0) { matrix tmp = pow(A, e/2); return mul(tmp, tmp); } else { matrix tmp = pow(A, e-1); return mul(A, tmp); } } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, T; ll X, A, B, C; cin >> N; cin >> X >> T >> A >> B >> C; MOD = C; matrix mat(2, vec(2)); mat[0][0] = A, mat[0][1] = B, mat[1][1] = 1; ll ans = 0; mat = pow(mat, T); for (int i = 0; i < N; i++) { ans += X; X = mat[0][0]*X + mat[0][1]; X %= C; } cout << ans << endl; return 0; }