题目描述 Description
给你6个数，m, a, c, x0, n, g
Xn+1 = ( aXn + c ) mod m，求Xn
m, a, c, x0, n, g<=10^18
输入描述 Input Description
一行六个数 m, a, c, x0, n, g
输出描述 Output Description
输出一个数 Xn mod g
样例输入 Sample Input
11 8 7 1 5 3
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
int64按位相乘可以不要用高精度。
这尼玛都没个伪装啊
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstdio>
4 #include <cstring>
5 #include <algorithm>
6 using namespace std;
7 long long m, a, c, x0, n, g;
8 template <int A, int B>
9 struct matrix
10 {
11 long long v[A][B];
12 matrix(long long r = 0)
13 {
14 memset(v, 0, sizeof(v));
15 for (int i = 0; i < A && i < B; i++)
16 v[i][i] = r;
17 }
18 matrix(long long a[A][B])
19 {
20 memcpy(v, a, sizeof(a));
21 }
22 };
23 inline long long quickadd(long long a, long long b)
24 {
25 long long ans = 0;
26 for (; b; b >>= 1)
27 {
28 if (b & 1) ans = (ans + a) % m;
29 a = (a + a) % m;
30 }
31 return ans;
32 }
33 template <int A, int B, int C>
34 matrix <A, C> operator * (const matrix <A, B> &a, const matrix <B, C> &b)
35 {
36 matrix <A, C> ans;
37 for (int i = 0; i < A; i++)
38 for (int j = 0; j < C; j++)
39 {
40 long long v = 0;
41 for (int k = 0; k < B; k++)
42 v += quickadd(a.v[i][k], b.v[k][j]);
43 ans.v[i][j] = (v % m + m) % m;
44 }
45 return ans;
46 }
47 template <int A>
48 matrix <A, A> power(const matrix<A, A> &a, long long b)
49 {
50 matrix <A, A> ans = 1;
51 for (matrix<A, A> i = a; b; b >>= 1)
52 {
53 if (b & 1) ans = ans * i;
54 i = i * i;
55 }
56 return ans;
57 }
58
59 matrix <2, 2> w;
60 matrix <1, 2> x;
61 int main()
62 {
63 scanf("%lld%lld%lld%lld%lld%lld", &m, &a, &c, &x0, &n, &g);
64 w.v[0][0] = a;
65 w.v[1][0] = w.v[1][1] = 1;
66 x.v[0][0] = x0;
67 x.v[0][1] = c;
68 printf("%lld\n", (x * power(w, n)).v[0][0] % g);
69 return 0;
70 }