包含 6 个用空格分割的 m,a,c,X0,n 和 g,其中 a,c,X0 是非负整数,m,n,g 是正整数。
输出一个数,即 Xn mod g
- //It is made by ljh2000
- #include < iostream > #include < cstdlib > #include < cstring > #include < cstdio > #include < cmath > #include < algorithm > #include < ctime > #include < vector > #include < queue > #include < map > #include < set > #include < string > #include < complex > using namespace std;
- typedef long long LL;
- LL m,
- a,
- c,
- X0,
- n,
- g;
- struct Matrix {
- LL s[2][2];
- }
- A,
- B,
- ini;
- inline LL cheng(LL x, LL y) {
- LL r = 0;
- while (y > 0) {
- if (y & 1) r += x,
- r %= m;
- x += x;
- x %= m;
- y >>= 1;
- }
- return r;
- }
- inline Matrix operator * (Matrix q, Matrix qq) {
- Matrix tmp = ini;
- for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int l = 0; l < 2; l++) tmp.s[i][j] += cheng(q.s[i][l], qq.s[l][j]),
- tmp.s[i][j] %= m;
- return tmp;
- }
- inline LL getLL() {
- LL w = 0,
- q = 0;
- char c = getchar();
- while ((c < '0' || c > '9') && c != ' - ') c = getchar();
- if (c == ' - ') q = 1,
- c = getchar();
- while (c >= '0' && c <= '9') w = w * 10 + c - '0',
- c = getchar();
- return q ? -w: w;
- }
- inline void fast_pow(Matrix a, LL y) {
- B.s[0][0] = B.s[1][1] = 1;
- while (y > 0) {
- if (y & 1) B = B * a;
- a = a * a;
- y >>= 1;
- }
- }
- inline void work() {
- m = getLL();
- a = getLL();
- c = getLL();
- X0 = getLL();
- n = getLL();
- g = getLL();
- A.s[0][0] = a;
- A.s[0][1] = 0;
- A.s[1][0] = c;
- A.s[1][1] = 1;
- fast_pow(A, n);
- printf("%lld", ((cheng(X0, B.s[0][0]) + B.s[1][0]) % m) % g);
- }
- int main() {
- work();
- return 0;
- }
long double 黑科技:
- //It is made by ljh2000
- #include < iostream > #include < cstdlib > #include < cstring > #include < cstdio > #include < cmath > #include < algorithm > #include < ctime > #include < vector > #include < queue > #include < map > #include < set > #include < string > #include < complex > using namespace std;
- typedef long long LL;
- LL m,
- a,
- c,
- X0,
- n,
- g;
- struct Matrix {
- LL s[2][2];
- }
- A,
- B,
- ini;
- inline LL cheng(LL x, LL y) { //double快速乘法
- long double sum = (long double) x * y;
- long double d = (long double) sum / m;
- LL zz = d + 1e-6; //防止精度误差
- LL r = x * y - zz * m;
- r %= m;
- r += m;
- r %= m; //可以直接做,因为高位必然相等,而我只要long long部分的结果,而直接做相当于对2^64取模,没有问题
- return r;
- }
- inline Matrix operator * (Matrix q, Matrix qq) {
- Matrix tmp = ini;
- for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int l = 0; l < 2; l++) tmp.s[i][j] += cheng(q.s[i][l], qq.s[l][j]),
- tmp.s[i][j] %= m;
- return tmp;
- }
- inline LL getLL() {
- LL w = 0,
- q = 0;
- char c = getchar();
- while ((c < '0' || c > '9') && c != ' - ') c = getchar();
- if (c == ' - ') q = 1,
- c = getchar();
- while (c >= '0' && c <= '9') w = w * 10 + c - '0',
- c = getchar();
- return q ? -w: w;
- }
- inline void fast_pow(Matrix a, LL y) {
- B.s[0][0] = B.s[1][1] = 1;
- while (y > 0) {
- if (y & 1) B = B * a;
- a = a * a;
- y >>= 1;
- }
- }
- inline void work() {
- m = getLL();
- a = getLL();
- c = getLL();
- X0 = getLL();
- n = getLL();
- g = getLL();
- A.s[0][0] = a;
- A.s[0][1] = 0;
- A.s[1][0] = c;
- A.s[1][1] = 1;
- fast_pow(A, n);
- printf("%lld", ((cheng(X0, B.s[0][0]) + B.s[1][0]) % m) % g);
- }
- int main() {
- work();
- return 0;
- }
来源: